Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces

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

Dietrich Kuske, Paul Gastin

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

68Q25: Analysis of algorithms and problem complexity

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

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

03B44: Temporal logic

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