The Complexity of Boundedness for Guarded Logics

DOI10.1109/LICS.2015.36zbMath1401.03064OpenAlexW1566071135MaRDI QIDQ4635812

Thomas Colcombet, Balder ten Cate, Michael Vanden Boom, Michael Benedikt

Publication date: 23 April 2018

Published in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/lics.2015.36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (7)

A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Guarded Ontology-Mediated Queries

This page was built for publication: The Complexity of Boundedness for Guarded Logics