Automata can show PSpace results for description logics

DOI10.1016/j.ic.2008.03.006zbMath1149.68073OpenAlexW2111351089WikidataQ57383699 ScholiaQ57383699MaRDI QIDQ948069

Rafael Peñaloza, Franz Baader, Jan Hladík

Publication date: 8 October 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.006

zbMATH Keywords

complexityautomata theorydescription logicsPSpace

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in artificial intelligence (68T27) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

PS\textsc{pace} tableau algorithms for acyclic modalized \({\mathcal{ALC}}\) ⋮ Reasoning in fuzzy description logics using automata ⋮ Presburger Büchi tree automata with applications to logics with expressive counting ⋮ The complexity of computing the behaviour of lattice automata on infinite trees ⋮ Automata-Based Axiom Pinpointing ⋮ An Automata View to Goal-Directed Methods ⋮ Automata-based axiom pinpointing

Uses Software

• KL-ONE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Attributive concept descriptions with complements
• Proof methods for modal and intuitionistic logics
• Automata-theoretic techniques for modal logics of programs
• Relationships between nondeterministic and deterministic tape complexities
• Terminological reasoning is inherently intractable
• How to optimize proof-search in modal logics
• Optimizing description logic subsumption
• The Description Logic Handbook
• An overview of tableau algorithms for description logics

This page was built for publication: Automata can show PSpace results for description logics