A Direct Equivalence-Testing Algorithm for SLRs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10454296" target="_blank" >RIV/00216208:11320/22:10454296 - isvavai.cz</a>

Výsledek na webu

<a href="https://isaim2022.cs.ou.edu/papers/ISAIM2022_Boolean_Cepek_Weigle.pdf" target="_blank" >https://isaim2022.cs.ou.edu/papers/ISAIM2022_Boolean_Cepek_Weigle.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Direct Equivalence-Testing Algorithm for SLRs

Popis výsledku v původním jazyce

In this paper we study the recently introduced switch-list representations (SLRs) of Boolean functions. An SLR is a compressed truth table representation of a Boolean function: we only store the function value of the first row, and a list of switches (Boolean vectors whose function value differs from the value of the preceding vector). The paper (Čepek and Chromý 2020) systematically studies the properties of SLRs and among other results gives polynomial time algorithms for all standard queries investigated in the Knowledge Compilation Map (Darwiche and Marquis 2002). In particular, the equivalence query (EQ) is implemented in (Čepek and Chromý 2020) by first compiling both input SLRs into OBDDs and then running the EQ query on the constructed OBDDs. In this short note we present an algorithm that answers the EQ query directly by manipulating the input SLRs (hence eliminating the compilation step into OBDD) which improves the time complexity of the procedure.

Název v anglickém jazyce

A Direct Equivalence-Testing Algorithm for SLRs

Popis výsledku anglicky

In this paper we study the recently introduced switch-list representations (SLRs) of Boolean functions. An SLR is a compressed truth table representation of a Boolean function: we only store the function value of the first row, and a list of switches (Boolean vectors whose function value differs from the value of the preceding vector). The paper (Čepek and Chromý 2020) systematically studies the properties of SLRs and among other results gives polynomial time algorithms for all standard queries investigated in the Knowledge Compilation Map (Darwiche and Marquis 2002). In particular, the equivalence query (EQ) is implemented in (Čepek and Chromý 2020) by first compiling both input SLRs into OBDDs and then running the EQ query on the constructed OBDDs. In this short note we present an algorithm that answers the EQ query directly by manipulating the input SLRs (hence eliminating the compilation step into OBDD) which improves the time complexity of the procedure.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-19463S" target="_blank" >GA19-19463S: Reprezentace booleovských funkcí úplné vzhledem k jednotkové propagaci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů