Automata can show PSpace results for description logics

DOI10.1016/J.IC.2008.03.006MaRDI QIDQ948069zbMATH OpenOpenAlexWikidataFDO

Authors Franz Baader, Rafael Peñaloza, 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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in artificial intelligence (68T27)

Recommendations

• scientific article; zbMATH DE number 2063024
• scientific article; zbMATH DE number 5674817
• Automated Deduction – CADE-19
• An overview of tableau algorithms for description logics
• Practical reasoning for very expressive description logics

Cites work

• scientific article; zbMATH DE number 5674817 (Why is no real title available?)
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• scientific article; zbMATH DE number 1765664 (Why is no real title available?)
• scientific article; zbMATH DE number 1405451 (Why is no real title available?)
• An overview of tableau algorithms for description logics
• Attributive concept descriptions with complements
• Automata-theoretic techniques for modal logics of programs
• How to optimize proof-search in modal logics
• Modal logic
• Optimizing description logic subsumption
• Proof methods for modal and intuitionistic logics
• Relationships between nondeterministic and deterministic tape complexities
• Terminological reasoning is inherently intractable
• The Description Logic Handbook

Cited in

(7)

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

Describes a project that uses

Uses Software

• KL-ONE

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q948069)