Boolean Nearest Neighbor Language in the Knowledge Compilation Map
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10510415" target="_blank" >RIV/00216208:11320/25:10510415 - isvavai.cz</a>
Výsledek na webu
<a href="https://proceedings.kr.org/2025/24/kr2025-0024-cepek-et-al.pdf" target="_blank" >https://proceedings.kr.org/2025/24/kr2025-0024-cepek-et-al.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.24963/kr.2025/24" target="_blank" >10.24963/kr.2025/24</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Boolean Nearest Neighbor Language in the Knowledge Compilation Map
Popis výsledku v původním jazyce
The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turán. A BNN representation of f is a pair (P, N) of sets of Boolean vectors (called positive and negative prototypes) where f (x) = 1 for every positive prototype x ELEMENT OF P, f (x) = 0 for every negative prototype x ELEMENT OF N, and the value f(x) for x NOT AN ELEMENT OF P UNION N is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.
Název v anglickém jazyce
Boolean Nearest Neighbor Language in the Knowledge Compilation Map
Popis výsledku anglicky
The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turán. A BNN representation of f is a pair (P, N) of sets of Boolean vectors (called positive and negative prototypes) where f (x) = 1 for every positive prototype x ELEMENT OF P, f (x) = 0 for every negative prototype x ELEMENT OF N, and the value f(x) for x NOT AN ELEMENT OF P UNION N is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2025
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
KR '25: Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning
ISBN
978-1-956792-08-9
ISSN
—
e-ISSN
—
Počet stran výsledku
10
Strana od-do
240-249
Název nakladatele
ACM
Místo vydání
Melbourne Australia
Místo konání akce
Melbourne Australia
Datum konání akce
11. 11. 2025
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—