First Steps Towards Taming Description Logics with Strings

Abstract We consider the description logic \(\mathcal {A}\mathcal {L}\mathcal {C}\mathcal {F}^{\mathcal {P}}(\mathcal {D}_{\varSigma })\) over the concrete domain \(\mathcal {D}_{\varSigma } = (\varSigma ^*, \prec, =, (=_{\mathfrak {w}})_{\mathfrak {w}\in \varSigma ^*})\), where \(\prec \) is the strict prefix order over finite strings in \(\varSigma ^*\). Using an automata-based approach, we show that the concept satisfiability problem w. r. t. general TBoxes for \(\mathcal {A}\mathcal {L}\mathcal {C}\mathcal {F}^{\mathcal {P}}(\mathcal {D}_{\varSigma })\) is ExpTime -complete for all finite alphabets \(\varSigma \). As far as we know, this is the first complexity result for an expressive description logic with a nontrivial concrete domain on strings.

Authors

• Stéphane Demri
• Karin Quaas

Keywords

No keywords are indexed for this paper.