2012 · 56 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationAutomata TheoryAutomated ReasoningComputational ModelsDescription LogicsFinite-state MachinesModel TheoryAutomata SimulationAutomata-theoretic CharacterizationsAutomata-theoretic SemanticsConservative ExtensionsExpressive Description LogicsFinite Automata TheoryInterpolation In Description LogicsLightweight Description Logics
We study (i) uniform interpolation for TBoxes that are formulated in the lightweight description logic EL and (ii) EL-approximations of TBoxes formulated in more expressive languages. In both cases, we give modeltheoretic characterizations based on simulations and cartesian products, and we develop algorithms that decide whether interpolants and approximants 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. 1
17
Franz Baader, Sebastian Brandt, Carsten Lutz · 2005 · 869 citations · Full text
Knowledge compilation and theory approximation
Bart Selman, Henry Kautz · Journal of the ACM · 1996 · 303 citations · Full text
Carsten Lutz, Frank Wolter · Journal of Symbolic Computation · 2009 · 125 citations