Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic

DOI10.1142/S0129054118500028zbMath1387.68136arXiv1510.08786OpenAlexW2962838432WikidataQ130102166 ScholiaQ130102166MaRDI QIDQ4639929

Martin Lück

Publication date: 14 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.08786

zbMATH Keywords

computational complexitytemporal logicsatisfiabilityfragmentsCTL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Temporal logic (03B44)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Generalized modal satisfiability
• A near-optimal method for reasoning about action
• Propositional dynamic logic of regular programs
• On the Lambert \(w\) function
• 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
• Decision procedures and expressiveness in the temporal logic of branching time
• Model Checking CTL is Almost Always Inherently Sequential
• Extremal Combinatorics
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• “Sometimes” and “not never” revisited
• The complexity of propositional linear temporal logics
• Satisfiability problems for propositional calculi
• Alternation
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of theorem-proving procedures
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)