Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces

DOI10.1016/j.ic.2009.12.003zbMath1195.68069OpenAlexW2086380717MaRDI QIDQ988553

Paul Gastin, Dietrich Kuske

Publication date: 18 August 2010

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

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

zbMATH Keywords

complexity of MSO-definable local temporal logics over concurrent systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Temporal logic (03B44)

Related Items (6)

The complexity of model checking multi-stack systems ⋮ Computing the reveals relation in occurrence nets ⋮ Sound concurrent traces for online monitoring ⋮ An optimal construction of Hanf sentences ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Temporal logics for concurrent recursive programs: satisfiability and model checking

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating finite automata on \(\omega\)-words
• Local temporal logic is expressively complete for cograph dependence alphabets
• Difficult configurations -- on the complexity of LTrL
• Shrinking games and local formulas
• The monadic quantifier alternation hierarchy over grids and graphs
• Weak alternating automata are not that weak
• Mathematical Foundations of Computer Science 2003
• CONCUR 2005 – Concurrency Theory
• CONCUR 2003 - Concurrency Theory
• LATIN 2004: Theoretical Informatics

This page was built for publication: Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces