Counting on CTL\(^*\): On the expressive power of monadic path logic

DOI10.1016/S0890-5401(03)00104-4zbMath1019.03023OpenAlexW2158212536WikidataQ59556959 ScholiaQ59556959MaRDI QIDQ1398378

Alexander Rabinovich, Faron Moller

Publication date: 29 July 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00104-4

Mathematics Subject Classification ID

Logic in computer science (03B70) Temporal logic (03B44)

Related Items

Limiting Until in Ordered Tree Query Languages, Bisimulation equivalence and regularity for real-time one-counter automata, Complexity of modal logics with Presburger constraints, Bisimulation invariant monadic-second order logic in the finite, Reasoning About Substructures and Games, On temporal logic versus Datalog, Bisimulation Invariant Monadic-Second Order Logic in the Finite, \(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\), CTL\(^\ast\) with graded path modalities

Cites Work

• The monadic theory of order
• The first order properties of products of algebraic systems
• Rabin's uniformization problem
• The decision problem for branching time logic
• “Sometimes” and “not never” revisited
• Modest theory of short chains. I
• Modest theory of short chains. II
• Monadic second order logic on tree-like structures
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item