A Direct Equivalence-Testing Algorithm for SLRs
The result's identifiers
Result code in 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>
Result on the web
<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
—
Alternative languages
Result language
angličtina
Original language name
A Direct Equivalence-Testing Algorithm for SLRs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-19463S" target="_blank" >GA19-19463S: Boolean Representation Languages Complete for Unit Propagation</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů