Answering regular path queries in expressive description logics via alternating tree-automata
DOI10.1016/J.IC.2014.04.002zbMATH Open1360.68801DBLPjournals/iandc/CalvaneseEO14OpenAlexW2092103258WikidataQ64360035 ScholiaQ64360035MaRDI QIDQ2252521FDOQ2252521
Thomas Eiter, Diego Calvanese, Magdalena Ortiz
Publication date: 18 July 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.04.002
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Logic in artificial intelligence (68T27)
Cites Work
- Tractable reasoning and efficient query answering in description logics: The DL-Lite family
- Title not available (Why is that?)
- Propositional dynamic logic of regular programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decidability of SHIQ with complex role inclusion axioms
- Reasoning in description logics by a reduction to disjunctive datalog
- Alternating automata on infinite trees
- Title not available (Why is that?)
- Regular path queries with constraints
- Title not available (Why is that?)
- Automata-theoretic techniques for modal logics of programs
- An automata theoretic decision procedure for the propositional mu- calculus
- PSpace reasoning for graded modal logics
- Title not available (Why is that?)
- Equivalence of Datalog queries is undecidable
- Title not available (Why is that?)
- Conjunctive query containment and answering under description logic constraints
- Title not available (Why is that?)
- Rewriting of regular expressions and regular path queries
- Combining Horn rules and description logics in CARIN
- Data Complexity in the $\mathcal{EL}$ Family of Description Logics
- Title not available (Why is that?)
- Query Answering in Description Logics: The Knots Approach
- Logic for Programming, Artificial Intelligence, and Reasoning
- Data complexity of query answering in expressive description logics via tableaux
- Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
- Title not available (Why is that?)
- A tableau decision procedure for \(\mathcal{SHOIQ}\)
- Title not available (Why is that?)
- Cheap Boolean Role Constructors for Description Logics
- The Complexity of Enriched Mu-Calculi
- Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Cited In (8)
- How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
- CTL\(^\ast\) with graded path modalities
- Presburger Büchi tree automata with applications to logics with expressive counting
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
- On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
- Querying the Unary Negation Fragment with Regular Path Expressions.
- Answering regular path queries mediated by unrestricted \(\mathcal{SQ}\) ontologies
Uses Software
This page was built for publication: Answering regular path queries in expressive description logics via alternating tree-automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2252521)
