The complexity of PDL with interleaving

DOI10.1016/0304-3975(95)00095-XMaRDI QIDQ1351943zbMATH OpenOpenAlexFDO

Authors Alain J. Mayer, Larry J. Stockmeyer

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)

Recommendations

• PDL with Intersection and Converse Is 2EXP-Complete
• PDL with intersection and converse: satisfiability and infinite-state model checking
• The propositional dynamic logic of deterministic, well-structured programs
• 2-Exp Time lower bounds for propositional dynamic logics with intersection
• PDL with data constants

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3694622 (Why is no real title available?)
• scientific article; zbMATH DE number 3695102 (Why is no real title available?)
• scientific article; zbMATH DE number 3772936 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1142324 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A near-optimal method for reasoning about action
• Alternation
• Checking equivalences between concurrent systems of finite agents (extended abstract)
• Complexity measures for regular expressions
• Concurrent dynamic logic
• Deciding true concurrency equivalences on safe, finite nets
• On the complexity of iterated shuffle
• Propositional dynamic logic of flowcharts
• Propositional dynamic logic of regular programs

Cited in

(9)

• Exponential-size model property for PDL with separating parallel composition
• Complexity optimal decision procedure for a propositional dynamic logic with parallel composition
• Resource separation in dynamic logic of propositional assignments
• 2-Exp Time lower bounds for propositional dynamic logics with intersection
• Model checking propositional dynamic logic with all extras
• PDL with Intersection and Converse Is 2EXP-Complete
• A propositional dynamic logic for concurrent programs based on the \(\pi\)-calculus
• Propositional dynamic logic with storing, recovering and parallel composition
• A lower complexity bound for propositional dynamic logic with intersection

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

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