Non-standard knowledge representation languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10477486" target="_blank" >RIV/00216208:11320/23:10477486 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Non-standard knowledge representation languages

Popis výsledku v původním jazyce

Knowledge representation languages constitute different formalisms forrepresenting Boolean functions. A Boolean function on n variables is a mapping from f0; 1gn tof0; 1g. This concept naturally appears and is extensively used in several areas of mathematicsand computer science and has many applications to real life problems. Well known representationlanguages include various types of Boolean formulas (e.g. CNFs and DNFs), various types ofbinary decision diagrams (BDDs, FBDDs, OBDDs), and negational normal forms (NNF, DNNF,d-DNNF). A Boolean function can also be represented by a truth table or a list of models.The task of transforming one of the representations of a given function f into another representationof f (e.g. transforming a DNF into an OBDD or a DNNF into a CNF) is called knowledgecompilation. A comprehensive review paper on knowledge compilation [3] introduces a KnowledgeCompilation Map (KCM). KCM systematically investigates different representation languages withrespect to (1) their relative succinctness, (2) the complexity of common transformations, and (3)the complexity of common queries. The succinctness of representations roughly speaking describeshow large the output representation in language B is with respect to the size of the inputrepresentation in language A when compiling from A to B. A precise definition of this notion willbe given in the talk. Transformations include negation, conjunction, disjunction, conditioning, andforgetting. The complexity of such transformations may differ dramatically from trivial to NP-harddepending on the chosen representation language. The same is true for queries such as consistencycheck, validity check, clausal and sentential entailment, equivalence check, model counting, andmodel enumeration.The paper [1] included Pseudo-Boolean constraint (PBC) and Cardinality constraint (CARD)languages into KCM by adding them into the succinctness diagram, and by proving the complexitystatus of almost all queries and transformations introduced in [3]. The same was later achievedfor languages SL and SL&lt; based on switch list representations in [2]. Let us start by defining thetwo languages considered in the talk.

Název v anglickém jazyce

Non-standard knowledge representation languages

Popis výsledku anglicky

Knowledge representation languages constitute different formalisms forrepresenting Boolean functions. A Boolean function on n variables is a mapping from f0; 1gn tof0; 1g. This concept naturally appears and is extensively used in several areas of mathematicsand computer science and has many applications to real life problems. Well known representationlanguages include various types of Boolean formulas (e.g. CNFs and DNFs), various types ofbinary decision diagrams (BDDs, FBDDs, OBDDs), and negational normal forms (NNF, DNNF,d-DNNF). A Boolean function can also be represented by a truth table or a list of models.The task of transforming one of the representations of a given function f into another representationof f (e.g. transforming a DNF into an OBDD or a DNNF into a CNF) is called knowledgecompilation. A comprehensive review paper on knowledge compilation [3] introduces a KnowledgeCompilation Map (KCM). KCM systematically investigates different representation languages withrespect to (1) their relative succinctness, (2) the complexity of common transformations, and (3)the complexity of common queries. The succinctness of representations roughly speaking describeshow large the output representation in language B is with respect to the size of the inputrepresentation in language A when compiling from A to B. A precise definition of this notion willbe given in the talk. Transformations include negation, conjunction, disjunction, conditioning, andforgetting. The complexity of such transformations may differ dramatically from trivial to NP-harddepending on the chosen representation language. The same is true for queries such as consistencycheck, validity check, clausal and sentential entailment, equivalence check, model counting, andmodel enumeration.The paper [1] included Pseudo-Boolean constraint (PBC) and Cardinality constraint (CARD)languages into KCM by adding them into the succinctness diagram, and by proving the complexitystatus of almost all queries and transformations introduced in [3]. The same was later achievedfor languages SL and SL&lt; based on switch list representations in [2]. Let us start by defining thetwo languages considered in the talk.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů