Rudimentary Languages and Second‐Order Logic

DOI10.1002/malq.19970430315zbMath0874.03038OpenAlexW2129959868MaRDI QIDQ4351932

Malika More, Frédéric Olive

Publication date: 28 August 1997

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19970430315

zbMATH Keywords

monadic second-order logicspectrafinite model theorycomplexity classrudimentary languageslinear hierarchyrudimentary sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (8)

Arithmetical definability and computational complexity ⋮ Rudimentary relations and primitive recursion: A toolbox ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Fifty years of the spectrum problem: survey and new results ⋮ On subrecursive complexity of integration ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ On the expressive power of monadic least fixed point logic

Cites Work

• Theory of Formal Systems. (AM-47)
• A spectrum hierarchy
• Unnamed Item

This page was built for publication: Rudimentary Languages and Second‐Order Logic