Pure future local temporal logics are expressively complete for Mazurkiewicz traces

DOI10.1016/j.ic.2006.07.002zbMath1113.03016MaRDI QIDQ859824

Volker Diekert, Paul Gastin

Publication date: 22 January 2007

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

Full work available at URL: https://doi.org/10.1016/j.ic.2006.07.002

zbMATH Keywords

expressive completeness; concurrency; temporal logics; Mazurkiewicz traces; aperiodic trace language

Mathematics Subject Classification ID

03B70: Logic in computer science

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

03B44: Temporal logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logical definability on infinite traces
• First-order logic and star-free sets
• LTL is expressively complete for Mazurkiewicz traces
• Local temporal logic is expressively complete for cograph dependence alphabets
• On the expressive power of temporal logic
• From local to global temporal logics over Mazurkiewicz traces.
• An expressively complete linear time temporal logic for Mazurkiewicz traces
• A ν-calculus with local views for systems of sequential agents
• Star-free regular sets of ω-sequences
• TEMPORAL LOGICS FOR TRACE SYSTEMS: ON AUTOMATED VERIFICATION
• Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
• On finite monoids having only trivial subgroups
• Mathematical Foundations of Computer Science 2003
• CONCUR 2003 - Concurrency Theory
• LATIN 2004: Theoretical Informatics