The complexity of PDL with interleaving

DOI10.1016/0304-3975(95)00095-XzbMath0872.03016OpenAlexW2000261666MaRDI QIDQ1351943

Larry J. Stockmeyer, Alain J. Mayer

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00095-x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70)

Related Items (7)

A Propositional Dynamic Logic for Concurrent Programs Based on the π-Calculus ⋮ Exponential-Size Model Property for PDL with Separating Parallel Composition ⋮ Resource separation in dynamic logic of propositional assignments ⋮ Propositional Dynamic Logic with Storing, Recovering and Parallel Composition ⋮ Model checking propositional dynamic logic with all extras ⋮ Complexity Optimal Decision Procedure for a Propositional Dynamic Logic with Parallel Composition ⋮ 2-Exp Time lower bounds for propositional dynamic logics with intersection

Cites Work

• On the complexity of iterated shuffle
• A near-optimal method for reasoning about action
• Complexity measures for regular expressions
• Propositional dynamic logic of regular programs
• Deciding true concurrency equivalences on safe, finite nets
• Propositional dynamic logic of flowcharts
• Concurrent dynamic logic
• Alternation
• Checking equivalences between concurrent systems of finite agents (Extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of PDL with interleaving