On the decidability and complexity of identity knowledge representation

Autoren Klaus-Dieter Schewe
Qing Wang
Editoren S.-g. Lee et al.
Titel On the decidability and complexity of identity knowledge representation
Buchtitel Database Systems for Advanced Applications - Proc. DASFAA 2012, Part I
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 7238
ISBN 978-3-642-29037-4
Monat April
Jahr 2012
Seiten 288-302
SCCH ID# 1202
Abstract

Identity knowledge is the knowledge that relates to various aspects of the identification of real-world objects. It can be acquired through the process of identifying objects from a knowledge management point of view. In this paper we present a simple yet expressive framework for representing identity knowledge. As basic building blocks, knowledge patterns have the capability of capturing identity knowledge at an arbitrary level of abstraction. However, the combined use of pattern formula and pattern relation in knowledge patterns may yield disjunction and a restricted form of negation. We thus investigate the containment problem of knowledge patterns to find a decision procedure for containment and equivalence between knowledge patterns. Our result shows that the containment problem for knowledge patterns is not only decidable but also tractable.