Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws

DOI10.3233/FI-2009-0050MaRDI QIDQ3634006zbMATH OpenFDO

Authors Iain Stewart

Publication date 23 June 2009

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2009-0050

zbMATH Keywords

descriptive complexityLindström logicsprogram schemeszero-one laws

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Program schemes, queues, the recursive spectrum and zero-one laws
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Hierarchies in classes of program schemes
• Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays

Cited in

(9)

• On the power of built-in relations in certain classes of program schemes
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• An infinite hierarchy in a class of polynomial-time program schemes
• Program Schemes with Deep Pushdown Storage
• Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays
• Program schemes, queues, the recursive spectrum and zero-one laws
• Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
• Hierarchies in classes of program schemes
• Program schemes, arrays, Lindström quantifiers and zero-one laws

This page was built for publication: Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws

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