PDL with Intersection and Converse Is 2EXP-Complete

DOI10.1007/978-3-540-71389-0_15MaRDI QIDQ5758037zbMATH OpenOpenAlexFDO

Authors Stefan Göller, Markus Lohrey, Carsten Lutz

Publication date 7 September 2007

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-71389-0_15

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• PDL with intersection and converse: satisfiability and infinite-state model checking
• PDL with data constants
• 2-Exp Time lower bounds for propositional dynamic logics with intersection
• The complexity of PDL with interleaving
• Computer Science Logic

Cited in

(8)

• The complexity of PDL with interleaving
• Run-Time Monitoring of Electronic Contracts
• PDL with intersection and converse: satisfiability and infinite-state model checking
• Public announcement logic with distributed knowledge: expressivity, completeness and complexity
• Computer Science Logic
• A lower complexity bound for propositional dynamic logic with intersection
• 2-Exp Time lower bounds for propositional dynamic logics with intersection
• Satisfiability and completeness of converse-PDL replayed

This page was built for publication: PDL with Intersection and Converse Is 2EXP-Complete

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