Pure future local temporal logics are expressively complete for Mazurkiewicz traces

DOI10.1016/j.ic.2006.07.002zbMath1113.03016OpenAlexW2009852886MaRDI 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 completenessconcurrencytemporal logicsMazurkiewicz tracesaperiodic trace language

Mathematics Subject Classification ID

Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Temporal logic (03B44)

Related Items

A Lyndon's identity theorem for one-relator monoids ⋮ Computing the reveals relation in occurrence nets ⋮ A survey on the local divisor technique ⋮ The Schützenberger category of a semigroup. ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Temporal logics for concurrent recursive programs: satisfiability and model checking ⋮ Topology, monitorable properties and runtime verification ⋮ Star-free languages are Church-Rosser congruential ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Omega-rational expressions with bounded synchronization delay

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