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

DOI10.1112/S1461157000000371MaRDI QIDQ4827608zbMATH OpenOpenAlexFDO

Authors Iain 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)

Recommendations

• Hierarchies in classes of program schemes
• Logical and schematic characterization of complexity classes
• An infinite hierarchy in a class of polynomial-time program schemes
• Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws
• scientific article; zbMATH DE number 1796951

Cites work

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

Cited in

(6)

• On the power of deep pushdown stacks
• On the power of built-in relations in certain classes of program schemes
• An infinite hierarchy in a class of polynomial-time program schemes
• Program Schemes with Deep Pushdown Storage
• scientific article; zbMATH DE number 2084702 (Why is no real title available?)
• Hierarchies in classes of program schemes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4827608)