A lower complexity bound for propositional dynamic logic with intersection

MaRDI QIDQ5483005zbMATH OpenFDO

Authors Martin Lange

Publication date 15 August 2006

zbMATH Keywords

satisfiability

Mathematics Subject Classification ID

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

Recommendations

• 2-Exp Time lower bounds for propositional dynamic logics with intersection
• PDL with Intersection and Converse Is 2EXP-Complete
• Decision complexity of variants of propositional dynamic logic
• Complexity and expressivity of propositional dynamic logics with finitely many variables
• The complexity of PDL with interleaving

Cited in

(3)

• The complexity of hybrid logics over equivalence relations
• Model checking propositional dynamic logic with all extras
• 2-Exp Time lower bounds for propositional dynamic logics with intersection

This page was built for publication: A lower complexity bound for propositional dynamic logic with intersection

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