Boolean Nearest Neighbor Language in the Knowledge Compilation Map
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Boolean Nearest Neighbor Language in the Knowledge Compilation Map
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
KR '25: Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning
ISBN
978-1-956792-08-9
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
240-249
Publisher name
ACM
Place of publication
Melbourne Australia
Event location
Melbourne Australia
Event date
Nov 11, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—