Original title: Booleovské metody v kompilaci znalostí
Translated title: Boolean methods in knowledge compilation
Authors: Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
Document type: Master’s theses
Year: 2016
Language: eng
Abstract: [eng] [cze]
The open problem in knowledge compilation of whether the language PI is at least as succinct as MODS is answered in the negative. For this purpose a class of Boolean functions with a number of prime implicants that is superpolynomial in their number of false points is constructed. A lower bound (proving that PI is not at least as succinct as MODS), an upper bound (proving that the counterexample cannot yield an exponential separation of PI and MODS) and the precise number of the prime implicants of these functions is computed. Powered by TCPDF (www.tcpdf.org) V rámci práce je vyřešen otevřený problém o relativní úspornosti jazyků PI a MODS. Ukazuje se, že PI není alespoň tak úsporný jako MODS tím, že se konstruuje třída Booleovských funkcí s počtem primárních implikantů který je superpolynomiální vzhledem k počtu nulových bodů zkonstruovaných funkcí. Odvozuje se dolní mez (čím se dokazuje, že PI není alespoň tak úsporný jako MODS), horní mez (která ukazuje, že zkonstruovaný protipříklad nemůže poskytnout exponenciální separaci PI a MODS) a vzorec pro přesný počet primárních implikantů zkonstruovaných funkcí. Powered by TCPDF (www.tcpdf.org)
Keywords: Boolean functions; knowledge compilation; MODS; PI; primary implicants; Booleovské funkce; kompilace znalostí; MODS; PI; primární implikanty

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/83080

Permalink: http://www.nusl.cz/ntk/nusl-469315


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses