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

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

• 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

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

Cited in

(15)

• Polyadic dynamic logics for HPSG parsing
• The complexity of PDL with interleaving
• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• A goal-directed decision procedure for hybrid PDL
• Complexity optimal decision procedure for a propositional dynamic logic with parallel composition
• Exponential-size model property for PDL with separating parallel composition
• Modal restriction semigroups: towards an algebra of functions.
• PDL with intersection and converse: satisfiability and infinite-state model checking
• Temporal logics for concurrent recursive programs: satisfiability and model checking
• It is easy to be wise after the event: communicating finite-state machines capture first-order logic with ``happened before
• A canonical model construction for iteration-free PDL with intersection
• \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
• A lower complexity bound for propositional dynamic logic with intersection
• PDL with Intersection and Converse Is 2EXP-Complete
• Derivatives on graphs for the positive calculus of relations with transitive closure

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)