{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T22:44:38Z","timestamp":1775256278907,"version":"3.50.1"},"reference-count":19,"publisher":"Wiley","issue":"4-5","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2018,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We investigate the expressive power of two logics, both with the successor function: first\u2010order logic with an uninterpreted function, and existential monadic second order logic\u2014that is first\u2010order logic over words\u2014, with multiplication by a constant\n                    <jats:italic>b<\/jats:italic>\n                    . We prove that all\n                    <jats:italic>b<\/jats:italic>\n                    \u2010recognizable sets are spectra of those logics. Furthermore, it is proven that some encoding of the set of halting times of a non\u2010deterministic 2\u2010counter automaton is also a spectrum. This yields undecidability of the finite satisfiability problem for those logics. Finally, it is shown that first\u2010order logic with one uninterpreted function and successor can encode quickly increasing functions, such as the Knuth's up\u2010arrows.\n                  <\/jats:p>","DOI":"10.1002\/malq.201500070","type":"journal-article","created":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T03:12:41Z","timestamp":1540350761000},"page":"286-311","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spectra and satisfiability for logics with successor and a unary function"],"prefix":"10.1002","volume":"64","author":[{"given":"Arthur","family":"Milchior","sequence":"first","affiliation":[{"name":"Institut de Recherche en Informatique Fondamentale Centre National de la Recherche Scientifique &amp; Universit\u00e9 Paris Diderot \u2013 Paris 7 Case 7014 75205 Paris Cedex 13 France"},{"name":"Laboratoire d'Algorithmique, Complexit\u00e9 et Logique, EA 4219 Universit\u00e9 Paris\u2010Est Cr\u00e9teil Val de Marne 61, avenue du G\u00e9n\u00e9ral de Gaulle 94010 Cr\u00e9teil France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1165-y"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_8_4_1","first-page":"191","article-title":"Logic and p\u2010recognizable sets of integers","volume":"1","author":"Bruy\u00e8re V.","year":"1994","journal-title":"Bull. Belg. Math. Soc"},{"key":"e_1_2_8_5_1","unstructured":"P.Chocron P.Fontaine andC.Ringeissen A gentle non\u2010disjoint combination of satisfiability procedures in: Automated Reasoning 7th International Joint Conference IJCAR 2014 Held as Part of the Vienna Summer of Logic Vienna Austria July 19\u201322 2014 Proceedings Lecture Notes in Artificial Intelligence Vol.8562 edited byS.Demri D.Kapur andC.Weidenbach(Springer 2014) pp.122\u2013136."},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01746527"},{"key":"e_1_2_8_7_1","doi-asserted-by":"crossref","unstructured":"A.Durand R.Fagin andB.Loescher Spectra with only unary function symbols in: Computer Science Logic 11th International Workshop CSL '97 Annual Conference of the EACSL Aarhus Denmark August 23\u201029 1997 Selected Papers edited byM.NielsenandW.Thomas Lecture Notes in Computer Science Vol.1414(Springer 1998) pp.189\u2013202.","DOI":"10.1007\/BFb0028015"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl.1804020"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2355-7"},{"issue":"3","key":"e_1_2_8_10_1","first-page":"268","article-title":"Decidability of the theory of the linear ordering relation","volume":"6","author":"Ehrenfeucht A.","year":"1959","journal-title":"Not. Amer. Math. Soc."},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200051513"},{"key":"e_1_2_8_13_1","doi-asserted-by":"crossref","unstructured":"Y.GurevichandS.Shelah Spectra of monadic second\u2010order formulas with one unary function in: 18th IEEE Symposium on Logic in Computer Science (LICS 2003) 22\u201325 June 2003 Ottawa Canada Proceedings (IEEE Computer Society 2003) pp.291\u2013300.","DOI":"10.1109\/LICS.2003.1210069"},{"key":"e_1_2_8_14_1","volume-title":"Mathematics and Computer Science: Coping with Finiteness","author":"Knuth D. E.","year":"1976"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-170069"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"e_1_2_8_17_1","first-page":"92","volume-title":"Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticienes des Pays Slaves","author":"Presburger M.","year":"1930"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322137"},{"key":"e_1_2_8_19_1","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity, Progress in Theoretical Computer Science","author":"Straubing H.","year":"1994"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280812"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201500070","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201500070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T21:23:22Z","timestamp":1775251402000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201500070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":19,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["10.1002\/malq.201500070"],"URL":"https:\/\/doi.org\/10.1002\/malq.201500070","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,23]]},"assertion":[{"value":"2015-10-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}