Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
From MaRDI portal
Publication:5059700
DOI10.21146/2074-1472-2021-27-2-93-120OpenAlexW4200099530MaRDI QIDQ5059700
Mikhail Rybakov, Dmitry Shkatov
Publication date: 16 January 2023
Published in: Logical Investigations (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.21146/2074-1472-2021-27-2-93-120
undecidabilitysatisfiability problemarithmetic complexitylinear-time temporal logicrecursive enumerabilityfirst-order temporal logicvalidity problembranching-time temporal logicrestricted languagesalgorithmic classification problemquantified temporal logic
Related Items (3)
Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Computational complexity of theories of a binary predicate with a small number of variables
Uses Software
Cites Work
- On intuitionistic modal and tense logics and their classical companion logics: topological semantics and bisimulations
- Elements of finite model theory.
- Quantification in nonclassical logic. Volume I.
- Concerning the semantic consequence relation in first-order temporal logic
- The power of temporal proofs
- The complexity of reasoning about knowledge and time. I: Lower bounds
- Incompleteness of first-order temporal logic with until
- On modal logic with an intuitionistic base
- On some intuitionistic modal logics
- Propositional dynamic logic of regular programs
- Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications
- Many-dimensional modal logics: theory and applications
- Decidable fragments of first-order temporal logics
- A survey of temporal extensions of description logics
- Complexity and expressivity of branching- and alternating-time temporal logics with finitely many variables
- The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
- On the feasibility of checking temporal integrity constraints
- Decision procedures and expressiveness in the temporal logic of branching time
- Axiomatic systems and topological semantics for intuitionistic temporal logic
- 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
- A general method for proving decidability of intuitionistic modal logics
- Temporal Logics in Computer Science
- Tableau-based decision procedures for logics of strategic ability in multiagent systems
- LTL over description logic axioms
- Monodic Fragments of First-Order Temporal Logics: 2000–2001 A.D.
- A Temporal Logic Approach to Binding-Time Analysis
- A modal analysis of staged computation
- Finite Kripke models and predicate logics of provability
- 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
- Alternating-time temporal logic
- ATL* Satisfiability Is 2EXPTIME-Complete
- Tableau-Based Procedure for Deciding Satisfiability in the Full Coalitional Multiagent Epistemic Logic
- Complexity of intuitionistic propositional logic and its fragments
- The complexity of propositional linear temporal logics
- On formulas of one variable in intuitionistic propositional calculus
- The Undecidability of Monadic Modal Quantification Theory
- On languages with two variables
- Complexity of products of modal logics
- Undecidability of modal and intermediate first-order logics with two individual variables
- On the Decision Problem for Two-Variable First-Order Logic
- The intuitionistic temporal logic of dynamical systems
- Logic in Computer Science
- Tableau-based decision procedure for the multiagent epistemic logic with all coalitional operators for common and distributed knowledge
- Undecidability of the Logic of Partial Quasiary Predicates
- Complexity and expressivity of propositional dynamic logics with finitely many variables
- A Decidable Intuitionistic Temporal Logic
- Recursive enumerability and elementary frame definability in predicate modal logic
- Algorithmic properties of first-order modal logics of finite Kripke frames in restricted languages
- Intuitionistic Linear Temporal Logics
- An intuitionistic axiomatization of `eventually'
- Complexity of finite-variable fragments of propositional modal logics of symmetric frames
- Computer Science Logic
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Complexity of finite-variable fragments of products with K
- Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
