SL reprezentace Booleovských funkcí vzhedem k nestandardním uspořádáním pravdivostní tabulky.

• Thesis title in Czech: SL reprezentace Booleovských funkcí vzhedem k nestandardním uspořádáním pravdivostní tabulky.
• Thesis title in English: SL representations of Boolean functions with respect to non-standard orderings of the truth table.
• Key words: Reprezentace Booleovských funkcí|Efektivní algoritmy|Standardní dotazy
• English key words: Representations of Boolean functions|Efficient algorithms|Standard queries
• Academic year of topic announcement: 2024/2025
• Thesis type: diploma thesis
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: prof. RNDr. Ondřej Čepek, Ph.D.

Guidelines

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 study non-standards orderings of the truth table and find out which orderings have interesting or useful properties with respect to SLRs. In particular it should be studied which queries and transformations can be implemented in polynomial time on such non-standard SLRs. The work should be mostly theoretical - study of different non-standard orderings, design of algorithms (for queries and transformations) and analysis of their properties (in particular of their time complexity).

References

Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal Of Artificial 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.