The Complexity of Abduction for Equality Constraint Languages
The Complexity of Abduction for Equality Constraint Languages
复制标题
等式约束语言的溯因复杂性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Michał Wrona
中科院分区：
文献类型：
--
作者：
Johannes Schmidt;Michał Wrona
溯因法是一种非单调推理的形式，它根据一些知识基础为观察到的现象寻找解释。文献中研究的溯因问题的一种形式是由二元域上的结构Gamma参数化的命题溯因问题。在这种情况下，知识库是Gamma上的一组约束，其表现和解释是命题公式。
Abduction is a form of nonmonotonic reasoning that looks for an explanation for an observed manifestation according to some knowledge base. One form of the abduction problem studied in the literature is the propositional abduction problem parameterized by a structure Gamma over the two-element domain. In that case, the knowledge base is a set of constraints over Gamma, the manifestation and explanation are propositional formulas.
In this paper, we follow a similar route. Yet, we consider abduction over infinite domain. We study the equality abduction problem parameterized by a relational first-order structure Gamma over the natural numbers such that every relation in Gamma is definable by a Boolean combination of equalities, a manifestation is a literal of the form (x = y) or (x != y), and an explanation is a set of such literals. Our main contribution is a complete complexity characterization of the equality abduction problem. We prove that depending on Gamma, it is Sigma^P_2-complete, or NP-complete, or in P.