Characterizing the {S}emantics of {T}erminological {C}ycles in {$\cal A\!L\!N\!$} using {F}inite {A}utomata

R. KüstersR. Küsters

$Characterizing the {S}emantics of {T}erminological {C}ycles in {$\cal A\!L\!N\!$} using {F}inite {A}utomata$

R. Küsters
Characterizing the {S}emantics of {T}erminological {C}ycles in {$\cal A\!L\!N\!$} using {F}inite {A}utomata
Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), 499--510, 1998. Morgan Kaufmann

Details
Bibtex

KurzfassungAbstract
The representation of terminological knowledge may naturally lead to terminological cycles. In
addition to descriptive semantics, the meaning of cyclic terminologies can also be captured by fixed-point semantics, namely, greatest and least fixed-point semantics. To gain a more profound understanding of these semantics and to obtain inference algorithms as well as complexity results for inconsistency, subsumption, and related inference tasks, this paper provides automata theoretic characterizations of these semantics. More precisely, the already existing results for \flnull{} are extended to the language \aln{}, which additionally allows for primitive negation and number-restric\-tions. Unlike \flnull, the language \aln{} allows to express inconsistent concepts, which makes non-trivial extensions of the characterizations and algorithms necessary. Nevertheless, the complexity of reasoning does not increase when going from \flnull{} to \aln{}. This distinguishes \aln{} from the very expressive languages with fixed-point operators proposed in the literature. It will be shown, however, that cyclic \aln{}-terminologies are expressive enough to capture
schemas in certain semantic data models.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Kuesters-KR-1998,
  author = {R. {K{\"u}sters}},
  booktitle = {Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98)},
  pages = {499--510},
  publisher = {Morgan Kaufmann},
  title = {Characterizing the {S}emantics of {T}erminological {C}ycles in {$\cal A\!L\!N\!$} using {F}inite {A}utomata},
  year = {1998},
}