Optimal complexity bounds for positive LTL games

DOI10.1007/3-540-45793-3_18MaRDI QIDQ4411828zbMATH OpenFDO

Authors Jerzy Marcinkowski, Tomasz Truderung

Publication date 10 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2471/24710262.htm

zbMATH Keywords

linear temporal logic

Mathematics Subject Classification ID

Temporal logic (03B44) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Recommendations

• Optimal bounds in parametric LTL games
• Optimal bounds in parametric LTL games
• A Hybrid Algorithm for LTL Games
• The parameterized complexity of positional games
• Optimal reachability for weighted timed games
• Optimization complexity of linear logic proof games
• On the complexity of counter reachability games
• On the Complexity of Counter Reachability Games
• Satisfiability games for branching-time logics

Cited in

(8)

• Optimal bounds in parametric LTL games
• Complexity of model checking MDPs against LTL specifications
• Deterministic generators and games for LTL fragments
• Computer Science Logic
• Playing games with boxes and diamonds.
• Semiring provenance for Büchi games: strategy analysis with absorptive polynomials
• Semiring provenance for Büchi games: strategy analysis with absorptive polynomials
• Games with winning conditions of high Borel complexity

This page was built for publication: Optimal complexity bounds for positive LTL games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4411828)