Název: Booleovské techniky v reprezentaci znalostí
Překlad názvu: Boolean techniques in Knowledge representation
Autoři: Chromý, Miloš ; Čepek, Ondřej (vedoucí práce) ; Mengel, Stefan (oponent) ; Kofroň, Jan (oponent)
Typ dokumentu: Disertační práce
Rok: 2020
Jazyk: eng
Abstrakt: [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...
Klíčová slova: Biclique satisfiability; Boolean functions; Interval representation; Knowledge compilation; SAT encoding; Switch-list representation; Bikliková splnitelnost; Booleovské funkce; Intervalová reprezentace; Kompilace znalostí; SAT kódování; Switch-list reprezentace

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/123569

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-437024


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce