Complexity of finite-variable fragments of propositional temporal and modal logics of computation

DOI10.1016/j.tcs.2022.04.056OpenAlexW4225423377MaRDI QIDQ2148903

Publication date: 24 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.056

zbMATH Keywords

computational complexity satisfiability problem finite-variable fragments modal logics branching-time temporal logics validity problem alternating-time temporal logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Temporal logic (03B44)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Quantification in nonclassical logic. Volume I.
Dynamic epistemic logic
FM 2009: Formal methods. Second world congress, Eindhoven, The Netherlands, November 2--6, 2009. Proceedings
The complexity of reasoning about knowledge and time. I: Lower bounds
On modal logic with an intuitionistic base
Propositional dynamic logic of regular programs
A modal perspective on the computational complexity of attribute value grammar
Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications
Many-dimensional modal logics: theory and applications
The decision problem of provability logic with only one atom
Complexity and expressivity of branching- and alternating-time temporal logics with finitely many variables
The complexity of propositional linear temporal logics in simple cases
The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
Multi-dimensional modal logic as a framework for spatio-temporal reasoning
Decision procedures and expressiveness in the temporal logic of branching time
Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
Complete axiomatization and decidability of alternating-time temporal logic
Logics of public communications
A general method for proving decidability of intuitionistic modal logics
Decidable fragments of first-order modal logics
Temporal Logics in Computer Science
Tableau-based decision procedures for logics of strategic ability in multiagent systems
Monodic Fragments of First-Order Temporal Logics: 2000–2001 A.D.
Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
Algorithmic properties of first-order modal logics of linear Kripke frames in restricted languages
ATL Satisfiability is Indeed EXPTIME-complete
Deciding $$\mathsf {ATL^*}$$ Satisfiability by Tableaux
Alternating-time temporal logic
ATL* Satisfiability Is 2EXPTIME-Complete
Multiagent Systems
Complexity of intuitionistic propositional logic and its fragments
The extensions of the modal logic K5
“Sometimes” and “not never” revisited
On formulas of one variable in intuitionistic propositional calculus
Undecidability of modal and intermediate first-order logics with two individual variables
Products of modal logics, part 1
Modal logics for reasoning about infinite unions and intersections of binary relations
Logic in Computer Science
Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
Complexity and expressivity of propositional dynamic logics with finitely many variables
Recursive enumerability and elementary frame definability in predicate modal logic
Algorithmic properties of first-order modal logics of finite Kripke frames in restricted languages
Complexity of finite-variable fragments of propositional modal logics of symmetric frames
The superintuitionistic predicate logic of finite Kripke frames is not recursively axiomatizable
Complexity of finite-variable fragments of products with K
Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages
Complexity of finite-variable fragments of products with non-transitive modal logics

This page was built for publication: Complexity of finite-variable fragments of propositional temporal and modal logics of computation