{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:03:32Z","timestamp":1759147412632},"reference-count":15,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2010order 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\u2010order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity.<\/jats:p>","DOI":"10.1002\/malq.19970430315","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T15:34:29Z","timestamp":1180452869000},"page":"419-426","source":"Crossref","is-referenced-by-count":10,"title":["Rudimentary Languages and Second\u2010Order Logic"],"prefix":"10.1002","volume":"43","author":[{"given":"Malika","family":"More","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"Bennett J. H. On Spectra. Doctoral Dissertation Princeton University Princeton N. J. 1962."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_2_1_4_2","first-page":"43","article-title":"Generalized first\u2010order spectra and polynomial\u2010time recognizable sets","volume":"7","author":"Fagin R.","year":"1974","journal-title":"SIAM\u2010Proceedings"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210117"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0022256"},{"key":"e_1_2_1_7_2","unstructured":"Harrow K. Sub\u2010elementary classes of functions and relations. Doctoral Dissertation New\u2010York University Department of Mathematics 1973."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786976"},{"key":"e_1_2_1_11_2","unstructured":"More M. Rudimentary representations of spectra. Pr\u00e9publication du LLAIC1 Num\u00e9ro 40 1994."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.2307\/2268308"},{"key":"e_1_2_1_13_2","series-title":"Annals of Math. Studies 47","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of Formal Systems","author":"Smullyan R.","year":"1961"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_15_2","unstructured":"Wood A. Some Problems in Logic and Number Theory and their Connections. Doctoral Dissertation University of Manchester 1981."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207018"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T05:37:55Z","timestamp":1696916275000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430315"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430315","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}