Premium
Rudimentary Languages and Second‐Order Logic
Author(s) -
More Malika,
Olive Frédéric
Publication year - 1997
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19970430315
Subject(s) - mathematics , descriptive complexity theory , recursion (computer science) , mathematical proof , complexity class , second order logic , hierarchy , first order logic , equivalence (formal languages) , formal language , class (philosophy) , computational complexity theory , algebra over a field , discrete mathematics , computer science , theoretical computer science , algorithm , higher order logic , pure mathematics , description logic , artificial intelligence , geometry , economics , market economy
The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity.