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

DOI10.2178/jsl/1129642115zbMath1100.03017OpenAlexW2044028378MaRDI QIDQ5486241

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)

Related Items (10)

Exponential-Size Model Property for PDL with Separating Parallel Composition ⋮ Unnamed Item ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Unnamed Item ⋮ Temporal logics for concurrent recursive programs: satisfiability and model checking ⋮ Unnamed Item ⋮ Polyadic dynamic logics for HPSG parsing ⋮ Complexity Optimal Decision Procedure for a Propositional Dynamic Logic with Parallel Composition ⋮ MODAL RESTRICTION SEMIGROUPS: TOWARDS AN ALGEBRA OF FUNCTIONS ⋮ A goal-directed decision procedure for hybrid PDL

Cites Work

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

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