Some relationships between logics of programs and complexity theory

DOI10.1016/0304-3975(88)90052-7zbMath0652.03028OpenAlexW2038233397MaRDI QIDQ1106839

Paweł Urzyczyn, Jerzy Tiuryn

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90052-7

zbMATH Keywords

recursive proceduresPSPACEPTIMEcomparative schematologyflow-diagrams with arrays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (11)

``During cannot be expressed by ``after ⋮ Complexity of proving program correctness ⋮ Contribution of Warsaw logicians to computational logic ⋮ Program Schemes with Deep Pushdown Storage ⋮ Computing on structures ⋮ On the expressive power of finitely typed and universally polymorphic recursive procedures ⋮ On strictly arithmetical completeness in logics of programs ⋮ On the power of deep pushdown stacks ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators ⋮ Logical and schematic characterization of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalences among logics of programs
• First-order dynamic logic
• Model theory
• Deterministic dynamic logic is strictly weaker than dynamic logic
• A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs
• Nontrivial definability by flow-chart programs
• Unbounded program memory adds to the expressive power of first-order programming logic
• Program Schemes with Pushdown Stores
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Classes of Program Schemata

This page was built for publication: Some relationships between logics of programs and complexity theory