Terminological Cycles in KL-ONE-based Knowledge Representation Languages

Cyclic definitions are often prohibited in terminological knowledge representation languages because, from a theoretical point of view, their semantics is not clear and, from a practical point of view, existing inference algorithms may go astray in the presence of cycles. In this paper, we shall consider terminological cycles in a very small KL-ONE-based language. For this language, the effect of the three types of semantics introduced by (Nebel 1987,1989,1989a) can be completely described with the help of finite automata. These descriptions pro-vide a rather intuitive understanding of terminologies with cyclic definitions and give insight into the essen-tial features of the respective semantics. In addition, one obtains algorithms and complexity results for subsump-tion determination. As it stands, the greatest fixed-point semantics comes off best. The characterization of this semantics is easy and has an obvious intuitive interpretation. Furthermore, important constructs- such as value-restriction with respect to the transitive or reflexive-transitive closure of a role- can easily be expressed. 1