Measuring Incompleteness under Multi-Valued Semantics by Partial MaxSAT Solvers

Yue MaYue Ma, Qingfeng ChangQingfeng Chang

Yue Ma, Qingfeng Chang
Measuring Incompleteness under Multi-Valued Semantics by Partial MaxSAT Solvers
The 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, to appear

Details
Bibtex

KurzfassungAbstract
Knowledge base metrics provide a useful way to analyze and compare knowledge bases. For example, inconsistency measurements have been proposed to distinguish different inconsistent knowledge bases. Whilst inconsistency degrees have been widely developed, the incompleteness of a knowledge base is rarely studied due to the difficulty of formalizing incompleteness. For this, we propose an incompleteness degree based on multi-valued semantics and show that it satisfies some desired properties. Moreover, we develop an algorithm to compute the proposed metric by reducing the problem to an instance of partial MaxSAT problem such that we can benefit from highly optimized partial MaxSAT solvers. We finally examine the approach over a set of knowledge bases from real applications, which experimentally shows that the proposed incompleteness metric can be computed pratically.
Bemerkung: Note: To appear.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ MaChang-Ecsquaru13,
  address = {Dresden, Germany},
  author = {Yue {Ma} and Qingfeng {Chang}},
  booktitle = {The 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty},
  note = {To appear.},
  title = {Measuring Incompleteness under Multi-Valued Semantics by Partial MaxSAT Solvers},
  year = {2013},
}