Deterministic propositional dynamic logic: finite models, complexity, and completeness

DOI10.1016/0022-0000(82)90018-6zbMath0512.03013OpenAlexW1987019087MaRDI QIDQ1839245

Amir Pnueli, Mordechai Ben-Ari, Joseph Y. Halpern

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90018-6

zbMATH Keywords

decision proceduremodal operatorsaccessibility relationsatomic programdeterministic propositional dynamic logicSegerberg's axioms for PDLsemantically complete

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Abstract data types; algebraic specification (68Q65)

Related Items (15)

A propositional dense time logic ⋮ Automata-theoretic techniques for modal logics of programs ⋮ Satisfiability in many-valued sentential logic is NP-complete ⋮ Propositional dynamic logic with quantification over regular computation sequences ⋮ Mechanizing common knowledge logic using COQ ⋮ Modal logics for reasoning about infinite unions and intersections of binary relations ⋮ Separation logics and modalities: a survey ⋮ Program schemata technique for propositional program logics: a 30-year history ⋮ Determinism and looping in combinatory PDL ⋮ Decision procedures and expressiveness in the temporal logic of branching time ⋮ The price of universality ⋮ MODAL RESTRICTION SEMIGROUPS: TOWARDS AN ALGEBRA OF FUNCTIONS ⋮ The propositional dynamic logic of deterministic, well-structured programs ⋮ A modal perspective on the computational complexity of attribute value grammar ⋮ An essay in combinatory dynamic logic

Cites Work

• Unnamed Item
• A near-optimal method for reasoning about action
• An elementary proof of the completeness of PDL
• Propositional dynamic logic of regular programs
• Decision complexity of variants of propositional dynamic logic

This page was built for publication: Deterministic propositional dynamic logic: finite models, complexity, and completeness