提出布尔最近邻语言在知识编译地图中的定位与计算特性。
Boolean Nearest Neighbor Language in the Knowledge Compilation Map
- 用正负原型定义布尔函数的最近邻表示
- 证明其在知识编译中比多种标准语言更紧凑
- 揭示其查询与转换的复杂性，适合逻辑推理研究者
布尔最近邻（BNN）表示由Hajnal、Liu和Turan最近提出。一个布尔函数f的BNN表示是一对布尔向量集合（称作正原型集P和负原型集N），使得对所有x∈P有f(x)=1，对所有x∈N有f(x)=0，而对x∉P∪N的情况，f(x)由距离最近的原型类型决定。本文主要目标是确定BNN语言在知识编译地图（KCM）中的位置。为此，我们推导出BNN语言与多个标准知识编译语言在表达紧凑性上的比较结果，并确定了针对BNN输入的多数标准查询与变换的复杂度状态。
原文摘要 · Abstract (English)
The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. 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 \in P$, $f(x)=0$ for all every negative prototype $x \in N$, and the value $f(x)$ for $x \not\in P \cup 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 derive results which compare the succinctness of the BNN language to several standard languages from KCM, and determine the complexity status of most standard queries and transformations for BNN inputs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。