Original title:
Booleovské techniky v reprezentaci znalostí
Translated title:
Boolean techniques in Knowledge representation
Authors:
Chromý, Miloš ; Čepek, Ondřej (advisor) ; Mengel, Stefan (referee) ; Kofroň, Jan (referee) Document type: Doctoral theses
Year:
2020
Language:
eng Abstract:
[eng][cze] Title: Boolean techniques in Knowledge representation Author: Miloš Chromý Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Ondřej Čepek, Ph.D., Department of Theoretical Com- puter Science and Mathematical Logic Abstract: In this thesis we will investigate switch-list representations of Boolean function and we will explore the biclique satisfiable formulas. Given a truth table representation of a Boolean function f the switch-list rep- resentation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. We include this type of representation in the Knowledge Compilation Map [Dar- wiche and Marquis, 2002] and argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard repre- sentations (such as CNF, DNF, and OBDD) with respect to their relative suc- cinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incom- parability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between...Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
Keywords:
Bikliková splnitelnost; Booleovské funkce; Intervalová reprezentace; Kompilace znalostí; SAT kódování; Switch-list reprezentace; Biclique satisfiability; Boolean functions; Interval representation; Knowledge compilation; SAT encoding; Switch-list representation
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/123569