AAAI Publications, Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
An Automata-Theoretic Approach to Uniform Interpolation and Approximation in the Description Logic EL
Carsten Lutz, Inanc Seylan, Frank Wolter

Last modified: 2012-05-17


We study (i) uniform interpolation for TBoxes that are formulated in the description logic EL and (ii) approximations of TBoxes formulated in more expressive languages. In both cases, we give model-theoretic characterizations based on simulations and cartesian products, and we develop algorithms that decide whether interpolants and approximations exist. We present a uniform approach to both problems, based on a novel amorphous automaton model called EL automata (EA). Using EAs, we also establish a simpler proof of the known result that conservative extensions of EL-TBoxes can be decided in ExpTime.


Description Logic, interpolation, approximation, conservative extension, automata

Full Text: PDF