Browse wiki
From International Center for Computational Logic
In Description Logics (DLs), both tableau- … In Description Logics (DLs), both tableau-based and automata-based algorithms are frequently used to show decidability and complexity results for basic inference problems such as concept satisfiability. Whereas tableau-based algorithms usually yield worst-case optimal algorithms in the case of PSPACE-complete logics, it is often very hard to design optimal tableau-based algorithms for EXPTIME-complete DLs. In contrast, the automata-based approach is usually well-suited to prove EXPTIME upper-bounds, but its direct application will usually also yield an EXPTIME-algorithm for a PSPACE-complete logic since the (tree) automaton constructed for a given concept is usually exponentially large. In the present paper, we formulate conditions under which an on-the-fly construction of such an exponentially large automaton can be used to obtain a PSPACE-algorithm. We illustrate the usefulness of this approach by proving a new PSPACE upper-bound for satisfiability of concepts w.r.t. acyclic terminologies in the DL SI.w.r.t. acyclic terminologies in the DL SI. +
@inproceedings{ BaaHlaPen-DL-07,
author = {F. {Baader} and J. {Hladik} and R. {Pe{\~n}aloza}},
booktitle = {Proceedings of the 2007 International Workshop on Description Logics},
editor = {D. {Calvanese} and E. {Franconi} and S. {Tessaris}},
series = {CEUR-WS},
title = {Blocking Automata for {PSPACE} {DLs}},
year = {2007},
}
author = {F. {Baader} and J. {Hladik} and R. {Pe{\~n}aloza}},
booktitle = {Proceedings of the 2007 International Workshop on Description Logics},
editor = {D. {Calvanese} and E. {Franconi} and S. {Tessaris}},
series = {CEUR-WS},
title = {Blocking Automata for {PSPACE} {DLs}},
year = {2007},
}
Baader +
Franz +
Franz Baader, J. Hladik, R. Peñaloza<br … Franz Baader, J. Hladik, R. Peñaloza<br/> '''[[LATPub370|<b>Blocking Automata for PSPACE DLs</b>]]''' <br/>__NOTOC__In D. Calvanese and E. Franconi and S. Tessaris, eds., <i>Proceedings of the 2007 International Workshop on Description Logics</i>, CEUR-WS, 2007<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub370|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BaaHlaPen-DL-07.pdf|Download]]:BaaHlaPen-DL-07.pdf|Download]] +
Franz Baader, J. Hladik, R. Peñaloza<br … Franz Baader, J. Hladik, R. Peñaloza<br/> '''[[LATPub370/en|<b>Blocking Automata for PSPACE DLs</b>]]''' <br/>__NOTOC__In D. Calvanese and E. Franconi and S. Tessaris, eds., <i>Proceedings of the 2007 International Workshop on Description Logics</i>, CEUR-WS, 2007<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub370|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BaaHlaPen-DL-07.pdf|Download]]:BaaHlaPen-DL-07.pdf|Download]] +
Display title of"Display title of" is a predefined property that can assign a distinct display title to an entity and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
Blocking Automata for PSPACE DLs +
Modification date"Zuletzt geändert <span style="font-size:small;">(Modification date)</span>" is a predefined property that corresponds to the date of the last modification of a subject and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
25. März 2015, 14:34:05 +
Has query"Hat Abfrage <span style="font-size:small;">(Has query)</span>" is a predefined property that represents meta information (in form of a <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">subobject</a>) about individual queries and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.