Difficult configurations -- on the complexity of LTrL

DOI10.1007/s10703-005-4593-zzbMath1075.68052OpenAlexW2027415891MaRDI QIDQ1774566

Igor Walukiewicz

Publication date: 17 May 2005

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10703-005-4593-z

zbMATH Keywords

global linear time temporal logic over traces

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items

Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces

Cites Work

• Unnamed Item
• Unnamed Item
• A stubborn attack on state explosion
• On undecidability of propositional temporal logics on trace systems
• Proving partial order properties
• A logical study of distributed transition systems
• Partial-order methods for the verification of concurrent systems. An approach to the state-explosion problem
• An expressively complete linear time temporal logic for Mazurkiewicz traces
• The complexity of propositional linear temporal logics