{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T22:44:54Z","timestamp":1752360294244,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005366","name":"University of Oslo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005366","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.\n<\/jats:p>","DOI":"10.1007\/s00153-020-00735-6","type":"journal-article","created":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T09:02:31Z","timestamp":1590224551000},"page":"77-104","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["First-order concatenation theory with bounded quantifiers"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6749-4004","authenticated-orcid":false,"given":"Lars","family":"Kristiansen","sequence":"first","affiliation":[]},{"given":"Juvenal","family":"Murwanashyaka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,23]]},"reference":[{"key":"735_CR1","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R., Senger, S.: Coding in the existential theory of concatenation. Archiv f\u00fcr mathematische Logik und Grundlagenforschung 26, 101\u2013106 (1986\/7)","DOI":"10.1007\/BF02017493"},{"key":"735_CR2","doi-asserted-by":"publisher","first-page":"625","DOI":"10.2307\/2272846","volume":"39","author":"J Corcoran","year":"1974","unstructured":"Corcoran, J., Frank, W., Maloney, M.: String theory. J. Symb. Log. 39, 625\u2013637 (1974)","journal-title":"J. Symb. Log."},{"key":"735_CR3","unstructured":"Day, J., Ganesh, V., He, P., Manea, F., Nowotka, D.: The satisfiability of extended word equations: the boundary between decidability and undecidability. arXiv:1802.00523 (2018)"},{"key":"735_CR4","first-page":"209","volume-title":"Hardware and Software: Verification and Testing. HVC 2012. LNCS 7857","author":"V Ganesh","year":"2012","unstructured":"Ganesh, V., Minnes, M., Solar-Lezama, A., Rinard, M.C.: Word equations with length constraints: what\u2019s decidable? In: Biere, A., Nahir, A., Vos, T. (eds.) Hardware and Software: Verification and Testing. HVC 2012. LNCS 7857, pp. 209\u2013226. Springer, Berlin (2012)"},{"key":"735_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s11225-005-2976-1","volume":"79","author":"A Grzegorczyk","year":"2005","unstructured":"Grzegorczyk, A.: Undecidability without arithmetization. Stud. Log. 79, 163\u2013230 (2005)","journal-title":"Stud. Log."},{"key":"735_CR6","first-page":"72","volume-title":"Andrzej Mostowski and Foundational Studies","author":"A Grzegorczyk","year":"2008","unstructured":"Grzegorczyk, A., Zdanowski, K.: Undecidability and concatenation. In: Ehrenfeucht, A., et al. (eds.) Andrzej Mostowski and Foundational Studies, pp. 72\u201391. IOS, Amsterdam (2008)"},{"key":"735_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3","volume-title":"Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic","author":"P Hajek","year":"1993","unstructured":"Hajek, P., Pudlak, P.: Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin (1993)"},{"key":"735_CR8","doi-asserted-by":"publisher","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: 2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). https:\/\/doi.org\/10.1109\/LICS40289.2017","DOI":"10.1109\/LICS40289.2017"},{"key":"735_CR9","unstructured":"Hermes, H.: Semiotik. Eine Theorie der Zeichengestalten als Grundlage f\u00fcr Untersuchungen von formalisierten Sprachen. Vol. 5 of \u201cForschungen zur Logik und zur Grundlegung der exakten Wissenschaften\u201d, Neue Folge, S. Hirzel, Leipzig (1938)"},{"key":"735_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s00153-014-0391-x","volume":"53","author":"K Higuchi","year":"2014","unstructured":"Higuchi, K., Horihata, Y.: Weak theories of concatenation and minimal essentially undecidable theories. Arch. Math. Log. 53, 835\u2013853 (2014)","journal-title":"Arch. Math. Log."},{"key":"735_CR11","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1215\/00294527-1715698","volume":"53","author":"Y Horihata","year":"2012","unstructured":"Horihata, Y.: Weak theories of concatenation and arithmetic. Notre Dame J. Form. Log. 53, 203\u2013222 (2012)","journal-title":"Notre Dame J. Form. Log."},{"key":"735_CR12","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Mignosi, F., Plandowski, W.: The expressibility of languages and relations by word equations. J. ACM 47, 483\u2013505 (2000)","journal-title":"J. ACM"},{"key":"735_CR13","first-page":"244","volume-title":"CiE 2018\u2014Sailing Routes in the World of Computation, LNCS 10936","author":"L Kristiansen","year":"2018","unstructured":"Kristiansen, L., Murwanashyaka, J.: Decidable and undecidable fragments of first-order concatenation theory. In: Manea, F., Miller, R.G., Nowokta, D. (eds.) CiE 2018\u2014Sailing Routes in the World of Computation, LNCS 10936, pp. 244\u2013253. Springer, Berlin (2018)"},{"key":"735_CR14","first-page":"542","volume-title":"TAMC 2007\u2013Theory and Applications of Models of Computation, LNCS 4484","author":"SA Kurtz","year":"2007","unstructured":"Kurtz, S.A., Simon, J.: The undecidability of the generalized Collatz problem. In: Cai, J.Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007\u2013Theory and Applications of Models of Computation, LNCS 4484, pp. 542\u2013553. Springer, Berlin (2007)"},{"key":"735_CR15","volume-title":"A Friendly Introduction to Mathematical Logic","author":"C Leary","year":"2015","unstructured":"Leary, C., Kristiansen, L.: A Friendly Introduction to Mathematical Logic, 2nd edn. Milne Library, SUNY Geneseo, Geneseo (2015)","edition":"2"},{"key":"735_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"GS Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Math. USSR-Sb. 32, 129\u2013198 (1977)","journal-title":"Math. USSR-Sb."},{"key":"735_CR17","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Ann. Math. 74, 437\u2013455 (1961)","journal-title":"Ann. Math."},{"key":"735_CR18","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"EL Post","year":"1946","unstructured":"Post, E.L.: A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52, 264\u2013268 (1946)","journal-title":"Bull. Am. Math. Soc."},{"key":"735_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2268308","volume":"11","author":"WV Quine","year":"1946","unstructured":"Quine, W.V.: Concatenation as a basis for arithmetic. J. Symb. Log. 11, 105\u2013114 (1946)","journal-title":"J. Symb. Log."},{"key":"735_CR20","doi-asserted-by":"publisher","first-page":"87","DOI":"10.2307\/2269066","volume":"4","author":"WV Quine","year":"1939","unstructured":"Quine, W.V.: Review of Hermes [9]. J. Symb. Log. 4, 87\u201388 (1939)","journal-title":"J. Symb. Log."},{"key":"735_CR21","unstructured":"Senger, S.: The existential theory of concatenation over a finite alphabet. Ph.D. Dissertation, Purdue University (1982)"},{"key":"735_CR22","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1215\/00294527-2008-029","volume":"50","author":"V Svejdar","year":"2009","unstructured":"Svejdar, V.: On interpretability in the theory of concatenation. Notre Dame J. Form. Log. 50, 87\u201395 (2009)","journal-title":"Notre Dame J. Form. Log."},{"key":"735_CR23","first-page":"261","volume":"1","author":"A Tarski","year":"1935","unstructured":"Tarski, A.: Der Wahrheitsbegriff in den formalisierten Sprachen. Stud. Philos. 1, 261\u2013405 (1935)","journal-title":"Stud. Philos."},{"key":"735_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1215\/00294527-2008-028","volume":"50","author":"A Visser","year":"2009","unstructured":"Visser, A.: Growing commas. A study of sequentiality and concatenation. Notre Dame J. Form. Log. 50, 61\u201385 (2009)","journal-title":"Notre Dame J. Form. Log."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-020-00735-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-020-00735-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-020-00735-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T23:05:51Z","timestamp":1621724751000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-020-00735-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,23]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["735"],"URL":"https:\/\/doi.org\/10.1007\/s00153-020-00735-6","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2020,5,23]]},"assertion":[{"value":"24 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}