An Automata-Theoretic Approach to Uniform Interpolation and Approximation in the Description Logic EL
An Automata-Theoretic Approach to Uniform Interpolation and Approximation in the Description Logic EL
复制标题
描述逻辑EL中一致插值和逼近的自动机理论方法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
F. Wolter
中科院分区：
文献类型：
--
作者：
C. Lutz;Inanç Seylan;F. Wolter
我们研究了（i）在轻巧描述逻辑EL和（ii）用更具表现力语言配制的Tbox的逻辑EL和（ii）EL-Approximation中提出的Tbox的均匀插值。在这两种情况下，我们都基于模拟和笛卡尔产品给出了模型理论特征，并且我们开发了决定插值和近似值是否存在的算法。我们基于一种称为El Automata（EA）的新型无定形自动机模型，为这两个问题提供了统一的方法。使用EAS，我们还建立了一个更简单的证明，证明可以在注册时间确定EL-Tbox的保守扩展的已知结果。
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 model-theoretic 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.