Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures

DOI10.1112/S1461157000000371zbMath1087.68567OpenAlexW2141421279MaRDI QIDQ4827608

Iain A. Stewart

Publication date: 18 November 2004

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.lms.ac.uk/jcm/6/lms2002-004/

zbMATH Keywords

polynomial-time solvable problems

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (2)

Program Schemes with Deep Pushdown Storage ⋮ On the power of deep pushdown stacks

Cites Work

• Logical and schematic characterization of complexity classes
• Reachability and the power of local ordering
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Logical Description of Monotone NP Problems
• Hierarchies in classes of program schemes
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Finite Model Theory

This page was built for publication: Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures