Pushing the EL envelope
作者： Franz Baader , Carsten Lutz , Sebastian Brandt
DOI:
关键词: Theoretical computer science 、 Envelope (motion) 、 Description logic 、 Mathematics 、 Conjunction (grammar) 、 Axiom 、 Algorithm 、 Set (abstract data type) 、 Value (computer science)
摘要: Recently, it has been shown that the small description logic (DL) EL, which allows for conjunction and existential restrictions, better algorithmic properties than its counterpart FL0, value restrictions. Whereas subsumption problem in FL0 becomes already intractable presence of acyclic TBoxes, remains tractable EL even with general concept inclusion axioms (GCIs). On one hand, we extend positive result by identifying a set expressive means can be added to without sacrificing tractability. other show basically all additions typical DL constructors GCIs make intractable, most cases EXPTIME-complete. In addition, is
ijcai.org
acm.org 参考文章(23)
Werner Nutt, Maurizio Lenzerini, Daniele Nardi, Francesco M. Donini, The Complexity of Concept Languages. principles of knowledge representation and reasoning. pp. 151- 162 ,(1991)
Klaus Schild, A correspondence theory for terminological logics: preliminary report international joint conference on artificial intelligence. pp. 466- 471 ,(1991)
Franz Baader, Terminological cycles in a description logic with existential restrictions international joint conference on artificial intelligence. pp. 325- 330 ,(2003)
Ian R. Horrocks, Alan L. Rector, Experience building a Large, Re-usable Medical Ontology using a Description Logic with Transitivity and Concept Inclusions ,(1997)
Franz Baader, Restricted Role-value-maps in a Description Logic with Existential Restrictions and Terminological Cycles. Description Logics. ,(2003)
Ian Horrocks, Ulrike Sattler, Decidability of SHIQ with complex role inclusion axioms international joint conference on artificial intelligence. pp. 343- 348 ,(2003)
Sebastian Brandt, Polynomial time reasoning in a Description Logic with existential restrictions, GCI axioms, and—what else? european conference on artificial intelligence. pp. 298- 302 ,(2004)
Diego Calvanese, Reasoning with Inclusion Axioms in Description Logics: Algorithms and Complexity. european conference on artificial intelligence. pp. 303- 307 ,(1996)
M. Hofmann, Proof-theoretic approach to description-logic logic in computer science. pp. 229- 237 ,(2005) , 10.1109/LICS.2005.38
Ian Horrocks, Using an Expressive Description Logic: FaCT or Fiction? principles of knowledge representation and reasoning. pp. 636- 649 ,(1998)