arXiv cs.AI

整数を持つ$ extmath{ALC}$のためのExpTime上限(拡張版)

An ExpTime Upper Bound for $\mathcal{ALC}$ with Integers (Extended Version)

http://arxiv.org/abs/2006.02078v1


この論文では、整数という具体的なドメインを持つ$ extmath{ALC}$の拡張における推論の複雑さの上限について探求しています。従来の$ extmath{ALC}$では、特に密なドメインにおける整合性の決定可能性に関する結果が多数存在していますが、非密なドメインに対する探求は限られていました。本研究では、整数間の比較を可能にする豊かなドメインを持つ$ extmath{ALC}$の拡張に着目し、オートマトン理論的手法を用いて整合性問題を単一指数時間で解決できることを証明します。この結果により、標準の$ extmath{ALC}$と同様の最悪ケースの複雑さに留まることが示されました。また、文献に知られている具体的なドメインを持つDLのいくつかとも適用可能で、一般的なTBoxをサポートし、機能的でない役割の経路を通じた値の比較も可能であることを示しています。