Logical and schematic characterization of complexity classes

DOI10.1007/BF01200263zbMath0790.68045MaRDI QIDQ1323362

Iain A. Stewart

Publication date: 2 June 1994

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

satisfiabilityterminationcomplexity classesPSPACEnormal form theoremsprogram schemes

Mathematics Subject Classification ID

Game theory (91A99) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures ⋮ On the power of built-in relations in certain classes of program schemes ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators ⋮ Logical and schematic characterization of complexity classes

Cites Work

• Some relationships between logics of programs and complexity theory
• Number of quantifiers is better than number of tape cells
• Upper and lower bounds for first order expressibility
• The polynomial-time hierarchy
• First-order dynamic logic
• Logical and schematic characterization of complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• On static logics, dynamic logics, and complexity classes
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Even Simple Programs Are Hard To Analyze
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Classes of Program Schemata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Logical and schematic characterization of complexity classes