2-Exp Time lower bounds for propositional dynamic logics with intersection

DOI10.2178/JSL/1129642115zbMATH Open1100.03017OpenAlexW2044028378MaRDI QIDQ5486241FDOQ5486241

Authors: Martin Lange, Carsten Lutz 

Publication date: 6 September 2006

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1129642115

Recommendations

• PDL with Intersection and Converse Is 2EXP-Complete
• A lower complexity bound for propositional dynamic logic with intersection
• PDL with intersection and converse: satisfiability and infinite-state model checking
• The propositional dynamic logic of deterministic, well-structured programs
• Decision complexity of variants of propositional dynamic logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Propositional dynamic logic of regular programs
• Title not available (Why is that?)
• Alternation
• Title not available (Why is that?)
• A Modal Perspective on Path Constraints
• Parallel action: Concurrent dynamic logic with independent modalities
• Propositional dynamic logic of looping and converse is elementarily decidable
• The complexity of concept languages
• Handbook of philosophical logic. Volume II: Extensions of classical logic
• PDL for ordered trees
• Looping vs. repeating in dynamic logic
• The complexity of PDL with interleaving
• PDL with negation of atomic programs

Cited In (14)

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• Title not available (Why is that?)
• PDL with intersection and converse: satisfiability and infinite-state model checking
• Exponential-size model property for PDL with separating parallel composition
• Complexity optimal decision procedure for a propositional dynamic logic with parallel composition
• Polyadic dynamic logics for HPSG parsing
• Temporal logics for concurrent recursive programs: satisfiability and model checking
• PDL with Intersection and Converse Is 2EXP-Complete
• A goal-directed decision procedure for hybrid PDL
• The complexity of PDL with interleaving
• It is easy to be wise after the event: communicating finite-state machines capture first-order logic with ``happened before
• A lower complexity bound for propositional dynamic logic with intersection
• Modal restriction semigroups: towards an algebra of functions.
• A canonical model construction for iteration-free PDL with intersection

This page was built for publication: 2-Exp Time lower bounds for propositional dynamic logics with intersection

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