Efficient implementation of queries and transformations on SL representations of Boolean functions.

• Název práce v češtině: Efektivní implementace dotazů a transformací na SL reprezentacích Booleovských funkcí.
• Název v anglickém jazyce: Efficient implementation of queries and transformations on SL representations of Boolean functions.
• Klíčová slova: Reprezentace Booleovských funkcí|Efektivní algoritmy|Standardní dotazy
• Klíčová slova anglicky: Representations of Boolean functions|Efficient algorithms|Standard queries
• Akademický rok vypsání: 2020/2021
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: prof. RNDr. Ondřej Čepek, Ph.D.
• Řešitel: James Weigle - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 13.04.2021
• Datum zadání: 13.04.2021
• Datum potvrzení stud. oddělením: 26.04.2022

Zásady pro vypracování

The student is expected to study the related literature from the area of knowledge compilation and then concentrate on switch-list representations (SLR) of Boolean functions. The aim of this research is to find efficient algorithms for standard queries performed directly on SLRs, in particular for equivalence testing (EQ) and sentential entailment (SE) for which only indirect algorithms (which compile the input SLRs into OBDDs and only then answer the query) are currently known. A systematic study of other queries and/or transformations is also possible. The work should be mostly theoretical - design of algorithms and analysis of their properties (in particular of their time complexity), however practical implementations and comparison studies of different implementations may be also considered.

Seznam odborné literatury

Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal Of Arti�ficial Intelligence Research, 17, 229-264.
Čepek,O.; Chromý,M. (2020) Properties of Switch-List Representations of Boolean Functions. Journal of Artificial Intelligence Research, 69, 501-529.