Logical and schematic characterization of complexity classes
type: Item
instance of: scholarly article
title: Logical and schematic characterization of complexity classes
zbMATH Open document ID: 0790.68045
DOI: 10.1007/BF01200263
author: Iain Stewart
published in: Acta Informatica
publication date: 1994-06-02T00:00:00Z
review text: We consider classes of well-known program schemes from a complexity theoretic viewpoint. We define logics which express all those problems solvable using our program schemes and show that the class of problems so solved or expressed coincides exactly with the complexity class of PSPACE (our problems are viewed as sets of finite structures over some vocabulary and, hence, they need not be encoded for input to our program schemes). We derive normal form theorems for our logics and use these normal form theorems to show that certain problems concerning acceptance and termination of our program schemes and satisfiability of our logical formulae are PSPACE-complete. Moreover, we show that a naturally-defined game problem, seemingly disjoint from logic and program schemes, is PSPACE-complete using the results described above. We also highlight similarities between the results of this paper and the literature, so providing the reader with an introduction to this area of research.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 91A99
zbMATH DE Number: 567323
zbMATH Keywords: complexity classes
zbMATH Keywords: program schemes
zbMATH Keywords: PSPACE
zbMATH Keywords: normal form theorems
zbMATH Keywords: termination
zbMATH Keywords: satisfiability
MaRDI profile type: Publication
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: On Classes of Program Schemata
cites work: Q4729378
cites work: Q4058132
cites work: Q4198056
cites work: First-order dynamic logic
cites work: Q4343990
cites work: On static logics, dynamic logics, and complexity classes
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Languages that Capture Complexity Classes
cites work: Q3974868
cites work: Nondeterministic Space is Closed under Complementation
cites work: Even Simple Programs Are Hard To Analyze
cites work: Q4185781
cites work: Q5573961
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Q4431234
cites work: The polynomial-time hierarchy
cites work: Some relationships between logics of programs and complexity theory
description: scientific article; zbMATH DE number 567323