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

DOI10.2178/JSL/1129642115MaRDI QIDQ5486241zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1936671 (Why is no real title available?)
• scientific article; zbMATH DE number 1556014 (Why is no real title available?)
• A Modal Perspective on Path Constraints
• Alternation
• Handbook of philosophical logic. Volume II: Extensions of classical logic
• Looping vs. repeating in dynamic logic
• PDL for ordered trees
• PDL with negation of atomic programs
• Parallel action: Concurrent dynamic logic with independent modalities
• Propositional dynamic logic of looping and converse is elementarily decidable
• Propositional dynamic logic of regular programs
• The complexity of PDL with interleaving
• The complexity of concept languages

Cited in

(14)

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

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)