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

satisfiability; termination; complexity classes; PSPACE; normal form theorems; program schemes

Mathematics Subject Classification ID

91A99: Game theory

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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, Context-sensitive transitive closure operators, Logical and schematic characterization of complexity classes, Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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