Some relationships between logics of programs and complexity theory

DOI10.1016/0304-3975(88)90052-7MaRDI QIDQ1106839zbMATH OpenOpenAlexFDO

Authors Jerzy Tiuryn, Paweł Urzyczyn

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

comparative schematologyflow-diagrams with arraysPSPACEPTIMErecursive procedures

Mathematics Subject Classification ID

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

Review text

The authors study some interesting connections between (open) problems in comparative schematology and logics of programs, on one hand, and problems in complexity theory on the other hand. As an example, PSPACE\(=PTIME\) iff flow-diagrams with arrays are of the same computational power as recursive procedures.

Recommendations

• Logical and schematic characterization of complexity classes
• scientific article; zbMATH DE number 3846863
• Equivalences among logics of programs
• LOGSPACE and PTIME characterized by programming languages
• Some open questions in the theory of program schemes and dynamic logics

Cites work

• A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Deterministic dynamic logic is strictly weaker than dynamic logic
• Equivalences among logics of programs
• First-order dynamic logic
• scientific article; zbMATH DE number 3778723 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3349780 (Why is no real title available?)
• Model theory
• Nontrivial definability by flow-chart programs
• On Classes of Program Schemata
• Program Schemes with Pushdown Stores
• Unbounded program memory adds to the expressive power of first-order programming logic

Cited in

(15)

• On the power of deep pushdown stacks
• ``During cannot be expressed by ``after
• On the expressive power of finitely typed and universally polymorphic recursive procedures
• Context-sensitive transitive closure operators
• Logical and schematic characterization of complexity classes
• On the relationship between TMS and logic programs
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• On strictly arithmetical completeness in logics of programs
• Contribution of Warsaw logicians to computational logic
• Program Schemes with Deep Pushdown Storage
• scientific article; zbMATH DE number 4049005 (Why is no real title available?)
• scientific article; zbMATH DE number 4103047 (Why is no real title available?)
• scientific article; zbMATH DE number 45116 (Why is no real title available?)
• Computing on structures
• Complexity of proving program correctness

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

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