{PSPACE} Automata for Description Logics

Jan HladikJan Hladik, Rafael PeñalozaRafael Peñaloza

Download

Jan Hladik, Rafael Peñaloza
{PSPACE} Automata for Description Logics
In B. {Parsia} and U. {Sattler} and D. {Toman}, eds., Proceedings of the 2006 International Workshop on Description Logics ({DL'06}), volume 189 of {CEUR-WS}, 2006

Details
Bibtex

KurzfassungAbstract
Tree automata are often used for satisfiability testing in the area of

 description logics, which usually yields EXPTIME complexity results. We
 examine conditions under which this result can be improved, and we define
 two classes of automata, called segmentable and
 weakly-segmentable, for which emptiness can be decided using space
 logarithmic in the size of the automaton (and thus polynomial in the size of
 the input). The usefulness of segmentable automata is demonstrated by
 reproving the known PSPACE result for satisfiability of ALC concepts with

respect to acyclic TBoxes.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ HlaPen-DL-06,
  author = {Jan {Hladik} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 2006 International Workshop on Description Logics ({DL'06})},
  editor = {B. {Parsia} and U. {Sattler} and D. {Toman}},
  series = {{CEUR-WS}},
  title = {{PSPACE} Automata for Description Logics},
  volume = {189},
  year = {2006},
}