The Complexity of CTL* + Linear Past

DOI10.1007/978-3-540-78499-9_14MaRDI QIDQ5458359zbMATH OpenOpenAlexFDO

Authors Laura Bozzelli

Publication date 11 April 2008

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78499-9_14

Mathematics Subject Classification ID

Temporal logic (03B44) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Past is for free: on the complexity of verifying linear temporal properties with past
• Past is for free: On the complexity of verifying linear temporal properties with past
• Results on alternating-time temporal logics with linear past
• On the Complexity of Branching-Time Logics
• scientific article; zbMATH DE number 2196601

Cites work

• A hierarchy of temporal logics with past
• Alternating automata on infinite trees
• An automata-theoretic approach to branching-time model checking
• scientific article; zbMATH DE number 3870578 (Why is no real title available?)
• scientific article; zbMATH DE number 4027441 (Why is no real title available?)
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 1500644 (Why is no real title available?)
• scientific article; zbMATH DE number 1775458 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Reasoning about infinite computations
• Specification in CTL + past for verification in CTL.
• “Sometimes” and “not never” revisited

Cited in

(13)

• Branching-time logics repeatedly referring to states
• Specification in CTL + past for verification in CTL.
• Alternating-time temporal logics with linear past
• A survey on temporal logics for specifying and verifying real-time systems
• scientific article; zbMATH DE number 1705170 (Why is no real title available?)
• Past is for free: on the complexity of verifying linear temporal properties with past
• On the Complexity of Branching-Time Logics
• \textit{Once} and \textit{for all}
• scientific article; zbMATH DE number 2038753 (Why is no real title available?)
• scientific article; zbMATH DE number 1536557 (Why is no real title available?)
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• Results on alternating-time temporal logics with linear past
• Reasoning about group responsibility for exceeding risk threshold in one-shot games

This page was built for publication: The Complexity of CTL* + Linear Past

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458359)