Some relationships between logics of programs and complexity theory
type: Item
instance of: scholarly article
title: Some relationships between logics of programs and complexity theory
zbMATH Open document ID: 0652.03028
DOI: 10.1016/0304-3975(88)90052-7
author: Jerzy Tiuryn
author: Paweł Urzyczyn
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4063081
zbMATH Keywords: comparative schematology
zbMATH Keywords: PSPACE
zbMATH Keywords: PTIME
zbMATH Keywords: flow-diagrams with arrays
zbMATH Keywords: recursive procedures
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90052-7
OpenAlex ID: W2038233397
cites work: Program Schemes with Pushdown Stores
cites work: Q3957927
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: On Classes of Program Schemata
cites work: Model theory
cites work: Q5625129
cites work: First-order dynamic logic
cites work: Q5592246
cites work: Equivalences among logics of programs
cites work: Q4185781
cites work: Deterministic dynamic logic is strictly weaker than dynamic logic
cites work: Unbounded program memory adds to the expressive power of first-order programming logic
cites work: A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs
cites work: Nontrivial definability by flow-chart programs
description: scientific article; zbMATH DE number 4063081