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

DOI10.1016/J.TCS.2022.04.056OpenAlexW4225423377MaRDI QIDQ2148903

Mikhail Rybakov, Dmitry Shkatov

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 complexitysatisfiability problemfinite-variable fragmentsmodal logicsbranching-time temporal logicsvalidity problemalternating-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