Rudimentary Languages and Second‐Order Logic

DOI10.1002/MALQ.19970430315MaRDI QIDQ4351932zbMATH OpenOpenAlexFDO

Authors 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

finite model theorymonadic second-order logicspectracomplexity classrudimentary languageslinear hierarchyrudimentary sets

Mathematics Subject Classification ID

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

Recommendations

• On second-order logic and natural language
• Languages of logic and their applications
• Pure second-order logic
• scientific article; zbMATH DE number 1550339
• scientific article; zbMATH DE number 1984507
• Logic, language and computation
• Logicism and Second-Order Logic
• Second-Order Logic and Foundations of Mathematics
• On higher-order logic and natural language
• AN APPLICATION OF FIRST-ORDER LOGIC TO THE STUDY OF RECOGNIZABLE LANGUAGES

Cites work

• scientific article; zbMATH DE number 2079027 (Why is no real title available?)
• A spectrum hierarchy
• Theory of Formal Systems. (AM-47)

Cited in

(9)

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

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

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