A simplified proof of \(DDL

DOI10.1016/0890-5401(89)90025-4zbMath0667.03021OpenAlexW2076739553MaRDI QIDQ1117214

Jerzy Tiuryn

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90025-4

zbMATH Keywords

determinismdynamic logicexpressive powernondeterministic flow-charts

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65)

Related Items (4)

Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\) ⋮ 1995 Annual Meeting of the Association for Symbol Logic ⋮ A difference in complexity between recursion and tail recursion ⋮ THICKET DENSITY

Cites Work

• Equivalences among logics of programs
• Model theory
• Deterministic dynamic logic is strictly weaker than dynamic logic
• Nontrivial definability by flow-chart programs
• Regular dynamic logic is not interpretable in deterministic context-free dynamic logic
• Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simplified proof of \(DDL<DL\)