On the Complexity of Branching-Time Logics

DOI10.1007/978-3-642-04027-6_38zbMath1257.03043OpenAlexW1559342273MaRDI QIDQ3644771

Volker Weber

Publication date: 12 November 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_38

zbMATH Keywords

alternating tree automataCTLbranching-time logiccomplexity of satisfiabilitypebble automataforgettable past

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hierarchy of temporal logics with past
• The temporal logic of branching time
• 25 years of model checking. History, achievements, perspectives
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Domino-tiling games
• Specification in CTL + past for verification in CTL.
• Decision procedures and expressiveness in the temporal logic of branching time
• Transitive closure logic, nested tree walking automata, and XPath
• “Sometimes” and “not never” revisited
• The Complexity of Tree Automata and Logics of Programs
• An automata-theoretic approach to branching-time model checking
• The Complexity of CTL* + Linear Past
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: On the Complexity of Branching-Time Logics