The complexity of boundedness for guarded logics

DOI10.1109/LICS.2015.36MaRDI QIDQ4635812zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Guarded fixed point logics and the monadic theory of countable trees.
• Guarded negation
• Guarded negation
• scientific article; zbMATH DE number 1341606
• Automata for Guarded Fixed Point Logics

Cited in

(19)

• Guarded quantification in least fixed point logic
• Guarded fixed point logics and the monadic theory of countable trees.
• 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
• scientific article; zbMATH DE number 6215728 (Why is no real title available?)
• Decidability results for the boundedness problem
• scientific article; zbMATH DE number 1341606 (Why is no real title available?)
• Automata for Guarded Fixed Point Logics
• Guarded Ontology-Mediated Queries
• scientific article; zbMATH DE number 7561474 (Why is no real title available?)
• Boundedness of conjunctive regular path queries
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Boundedness of Monadic FO over Acyclic Structures
• Guarded negation
• Guarded negation
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• Modal separation of fixpoint formulae
• On deciding the data complexity of answering linear monadic Datalog queries with ltl operators
• The complexity of defining and separating fixpoint formulae in modal logic

This page was built for publication: The complexity of boundedness for guarded logics

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