{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T00:44:19Z","timestamp":1782953059840,"version":"3.54.5"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032227294","type":"print"},{"value":"9783032227300","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22730-0_21","type":"book-chapter","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T16:25:16Z","timestamp":1776270316000},"page":"440-461","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Well-quasi-orderings on word languages"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3303-5368","authenticated-orcid":false,"given":"Nathan","family":"Lhote","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4205-327X","authenticated-orcid":false,"given":"Aliaume","family":"Lopez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4002-5491","authenticated-orcid":false,"given":"Lia","family":"Sch\u00fctze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,15]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Jonsson, B.: Verifying networks of timed processes. In: Proceedings of TACAS\u201998. vol.\u00a01384, pp. 298\u2013312. Springer (1998). https:\/\/doi.org\/10.1007\/BFb0054179","DOI":"10.1007\/BFb0054179"},{"key":"21_CR2","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., \u010cer\u0101ns, K., Tsay, B.J., Yih-Kuen: General decidability theorems for infinite-state systems. In: Proceedings of LICS\u201996. pp. 313\u2013321. IEEE (1996). https:\/\/doi.org\/10.1109\/LICS.1996.561359","DOI":"10.1109\/LICS.1996.561359"},{"key":"21_CR3","unstructured":"Allouche, J.P., Cassaigne, J., Shallit, J., Zamboni, L.Q.: A taxonomy of morphic sequences (2017), https:\/\/arxiv.org\/abs\/1711.10807"},{"key":"21_CR4","doi-asserted-by":"publisher","unstructured":"Allouche, J.P., Shallit, J.: The ubiquitous prouhet-thue-morse sequence. Discrete Mathematics and Theoretical Computer Science p. 1\u201316 (1999). https:\/\/doi.org\/10.1007\/978-1-4471-0551-0_1, http:\/\/dx.doi.org\/10.1007\/978-1-4471-0551-0_1","DOI":"10.1007\/978-1-4471-0551-0_1"},{"key":"21_CR5","doi-asserted-by":"publisher","unstructured":"Anand, A., Schmitz, S., Sch\u00fctze, L., Zetzsche, G.: Verifying unboundedness via amalgamation. In: Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science. LICS \u201924, Association for Computing Machinery, New York, NY, USA (2024).https:\/\/doi.org\/10.1145\/3661814.3662133, https:\/\/doi.org\/10.1145\/3661814.3662133","DOI":"10.1145\/3661814.3662133"},{"key":"21_CR6","doi-asserted-by":"publisher","unstructured":"Atminas, A., Lozin, V., Moshkov, M.: Wqo is decidable for factorial languages. Information and Computation 256, 321\u2013333 (Oct 2017). https:\/\/doi.org\/10.1016\/j.ic.2017.08.001, http:\/\/dx.doi.org\/10.1016\/j.ic.2017.08.001","DOI":"10.1016\/j.ic.2017.08.001"},{"key":"21_CR7","doi-asserted-by":"publisher","unstructured":"Bergstr\u00e4\u00dfer, P., Ganardi, M., Lin, A.W., Zetzsche, G.: Ramsey quantifiers in linear arithmetics. Proc. ACM Program. Lang. 8(POPL), 1\u201332 (2024). https:\/\/doi.org\/10.1145\/3632843, https:\/\/doi.org\/10.1145\/3632843","DOI":"10.1145\/3632843"},{"key":"21_CR8","doi-asserted-by":"publisher","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Vieweg+Teubner Verlag (1979). https:\/\/doi.org\/10.1007\/978-3-663-09367-1, http:\/\/dx.doi.org\/10.1007\/978-3-663-09367-1","DOI":"10.1007\/978-3-663-09367-1"},{"key":"21_CR9","doi-asserted-by":"publisher","unstructured":"Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. In: International Colloquium on Automata, Languages, and Programming. vol.\u00a040, pp. 71\u201379 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90162-8, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397585901628, eleventh International Colloquium on Automata, Languages and Programming","DOI":"10.1016\/0304-3975(85)90162-8"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Carton, O., Colcombet, T., Puppis, G.: An algebraic approach to mso-definability on countable linear orderings. The Journal of Symbolic Logic 83(3), 1147\u20131189 (2018), https:\/\/www.jstor.org\/stable\/26600366","DOI":"10.1017\/jsl.2018.7"},{"key":"21_CR11","doi-asserted-by":"publisher","unstructured":"Cassaigne, J., Karhum\u00e4ki, J.: Toeplitz words, generalized periodicity and periodically iterated morphisms. European Journal of Combinatorics 18(5), 497\u2013510 (Jul 1997). https:\/\/doi.org\/10.1006\/eujc.1996.0110, http:\/\/dx.doi.org\/10.1006\/eujc.1996.0110","DOI":"10.1006\/eujc.1996.0110"},{"key":"21_CR12","doi-asserted-by":"publisher","unstructured":"Daligault, J., Rao, M., Thomass\u00e9, S.: Well-quasi-order of relabel functions. Order 27(3), 301\u2013315 (September 2010). https:\/\/doi.org\/10.1007\/s11083-010-9174-0, http:\/\/dx.doi.org\/10.1007\/s11083-010-9174-0","DOI":"10.1007\/s11083-010-9174-0"},{"key":"21_CR13","unstructured":"Demeri, S., Finkel, A., Goubault-Larrecq, J., Schmitz, S., Schnoebelen, P.: Algorithmic aspects of wqo theory (mpri course) (2012), https:\/\/cel.archives-ouvertes.fr\/cel-00727025, course notes"},{"key":"21_CR14","doi-asserted-by":"publisher","unstructured":"Durand, F.: Decidability of uniform recurrence of morphic sequences. International Journal of Foundations of Computer Science 24(01), 123\u2013146 (2013). https:\/\/doi.org\/10.1142\/S0129054113500032","DOI":"10.1142\/S0129054113500032"},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"D\u017eamonja, M., Schmitz, S., Schnoebelen, P.: On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders, pp. 29\u201354. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-30229-0_2, https:\/\/doi.org\/10.1007\/978-3-030-30229-0_2","DOI":"10.1007\/978-3-030-30229-0_2"},{"key":"21_CR16","doi-asserted-by":"publisher","unstructured":"D\u2019Alessandro, F., Varricchio, S.: On well quasi-orders on languages, pp. 230\u2013241. Springer Berlin Heidelberg (2003).https:\/\/doi.org\/10.1007\/3-540-45007-6_18","DOI":"10.1007\/3-540-45007-6_18"},{"key":"21_CR17","doi-asserted-by":"publisher","unstructured":"D\u2019Alessandro, F., Varricchio, S.: Well quasi-orders, unavoidable sets, and derivation systems. RAIRO - Theoretical Informatics and Applications 40(3), 407\u2013426 (Jul 2006). https:\/\/doi.org\/10.1051\/ita:2006019, http:\/\/dx.doi.org\/10.1051\/ita:2006019","DOI":"10.1051\/ita:2006019"},{"key":"21_CR18","doi-asserted-by":"publisher","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society 16(1), 109\u2013114 (Feb 1965). https:\/\/doi.org\/10.1090\/s0002-9939-1965-0174934-9, http:\/\/dx.doi.org\/10.1090\/S0002-9939-1965-0174934-9","DOI":"10.1090\/s0002-9939-1965-0174934-9"},{"key":"21_CR19","doi-asserted-by":"publisher","unstructured":"Finkel, A., Gupta, E.: The well structured problem for presburger counter machines. In: Chattopadhyay, A., Gastin, P. (eds.) 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India. LIPIcs, vol.\u00a0150, pp. 41:1\u201341:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2019.41, https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.41","DOI":"10.4230\/LIPICS.FSTTCS.2019.41"},{"key":"21_CR20","doi-asserted-by":"publisher","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society 3, 326\u2013336 (1952). https:\/\/doi.org\/10.1112\/plms\/s3-2.1.326","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"21_CR21","doi-asserted-by":"publisher","unstructured":"de\u00a0Jongh, D., Parikh, R.: Well-partial orderings and hierarchies. Indagationes Mathematicae (Proceedings) 80(3), 195\u2013207 (1977). https:\/\/doi.org\/10.1016\/1385-7258(77)90067-1, http:\/\/dx.doi.org\/10.1016\/1385-7258(77)90067-1","DOI":"10.1016\/1385-7258(77)90067-1"},{"key":"21_CR22","doi-asserted-by":"publisher","unstructured":"Krivine, J.L.: Introduction to Axiomatic Set Theory. Springer Netherlands (1971). https:\/\/doi.org\/10.1007\/978-94-010-3144-8","DOI":"10.1007\/978-94-010-3144-8"},{"key":"21_CR23","doi-asserted-by":"publisher","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A 13(3), 297\u2013305 (Nov 1972). https:\/\/doi.org\/10.1016\/0097-3165(72)90063-5, http:\/\/dx.doi.org\/10.1016\/0097-3165(72)90063-5","DOI":"10.1016\/0097-3165(72)90063-5"},{"key":"21_CR24","doi-asserted-by":"publisher","unstructured":"Kunen, K.: Set Theory. Elsevier (1980). https:\/\/doi.org\/10.1016\/s0049-237x(08)x7037-5, http:\/\/dx.doi.org\/10.1016\/s0049-237x(08)x7037-5","DOI":"10.1016\/s0049-237x(08)x7037-5"},{"key":"21_CR25","doi-asserted-by":"publisher","unstructured":"Kuske, D.: Theories of orders on the set of words. RAIRO Theor. Informatics Appl. 40(1), 53\u201374 (2006). https:\/\/doi.org\/10.1051\/ITA:2005039, https:\/\/doi.org\/10.1051\/ita:2005039","DOI":"10.1051\/ITA:2005039"},{"key":"21_CR26","doi-asserted-by":"publisher","unstructured":"K\u0159\u00ed\u017e, I., Thomas, R.: Ordinal Types in Ramsey Theory and Well-Partial-Ordering Theory, p. 57\u201395. Springer Berlin Heidelberg (1990). https:\/\/doi.org\/10.1007\/978-3-642-72905-8_7, http:\/\/dx.doi.org\/10.1007\/978-3-642-72905-8_7","DOI":"10.1007\/978-3-642-72905-8_7"},{"key":"21_CR27","doi-asserted-by":"publisher","unstructured":"Lopez, A.: Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width. In: Gawrychowski, P., Mazowiecki, F., Skrzypczak, M. (eds.) 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0345, pp. 70:1\u201370:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2025).https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2025.70, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.MFCS.2025.70","DOI":"10.4230\/LIPIcs.MFCS.2025.70"},{"key":"21_CR28","doi-asserted-by":"publisher","unstructured":"Nicolas, F., Pritykin, Y.: On uniformly recurrent morphic sequences. International Journal of Foundations of Computer Science 20(05), 919\u2013940 (Oct 2009). https:\/\/doi.org\/10.1142\/s0129054109006966, http:\/\/dx.doi.org\/10.1142\/S0129054109006966","DOI":"10.1142\/s0129054109006966"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society 141, 1\u201335 (1969), http:\/\/www.jstor.org\/stable\/1995086","DOI":"10.1090\/S0002-9947-1969-0246760-1"},{"key":"21_CR30","doi-asserted-by":"publisher","unstructured":"Schmidt, D.: The relation between the height of a well-founded partial ordering and the order types of its chains and antichains. Journal of Combinatorial Theory, Series B 31(2), 183\u2013189 (Oct 1981). https:\/\/doi.org\/10.1016\/s0095-8956(81)80023-8, http:\/\/dx.doi.org\/10.1016\/S0095-8956(81)80023-8","DOI":"10.1016\/s0095-8956(81)80023-8"},{"key":"21_CR31","unstructured":"Schmitz, S.: Algorithmic Complexity of Well-Quasi-Orders. Habilitation \u00e0 diriger des recherches, \u00c9cole normale sup\u00e9rieure Paris-Saclay (Nov 2017), https:\/\/theses.hal.science\/tel-01663266"},{"key":"21_CR32","doi-asserted-by":"publisher","unstructured":"Schmitz, S.: The parametric complexity of lossy counter machines. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0132, pp. 129:1\u2013129:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.129, https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ICALP.2019.129","DOI":"10.4230\/LIPIcs.ICALP.2019.129"},{"key":"21_CR33","doi-asserted-by":"publisher","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of formal languages, pp. 389\u2013455. Springer (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5","DOI":"10.1007\/978-3-642-59136-5"},{"key":"21_CR34","doi-asserted-by":"publisher","unstructured":"Tromp, J., Shallit, J.: Subword complexity of a generalized thue-morse word. Information Processing Letters 54(6), 313\u2013316 (Jun 1995). https:\/\/doi.org\/10.1016\/0020-0190(95)00074-m, http:\/\/dx.doi.org\/10.1016\/0020-0190(95)00074-M","DOI":"10.1016\/0020-0190(95)00074-m"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22730-0_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T23:51:42Z","timestamp":1782949902000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22730-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032227294","9783032227300"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22730-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"15 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2026\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}