{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:58Z","timestamp":1740109378448,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T00:00:00Z","timestamp":1712793600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T00:00:00Z","timestamp":1712793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u00c7esk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-12790S19-12790S"],"award-info":[{"award-number":["19-12790S19-12790S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The notion of a\u00a0quasi-order generated by a\u00a0homomorphism from the semigroup of all words onto a\u00a0finite ordered semigroup was introduced by Bucher et al. (Theor. Comput. Sci. <jats:bold>40<\/jats:bold>, 131\u2013148 1985). It naturally occurred in their studies of derivation relations associated with a\u00a0given set of context-free rules, and they asked a\u00a0crucial question, whether the resulting relation is a\u00a0well quasi-order. We answer this question in the case of the quasi-order generated by a\u00a0semigroup homomorphism. We show that the answer does not depend on the homomorphism, but it is a\u00a0property of its image. Moreover, we give an algebraic characterization of those finite semigroups for which we get well quasi-orders. This characterization completes the structural characterization given by Kunc (Theor. Comput. Sci. <jats:bold>348<\/jats:bold>, 277\u2013293 2005) in the case of semigroups ordered by equality. Compared with Kunc\u2019s characterization, the new one has no structural meaning, and we explain why that is so. In\u00a0addition, we prove that the new condition is testable in polynomial time.<\/jats:p>","DOI":"10.1007\/s00224-024-10172-0","type":"journal-article","created":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T08:02:40Z","timestamp":1712822560000},"page":"380-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6513-5086","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Kl\u00edma","sequence":"first","affiliation":[]},{"given":"Jonatan","family":"Kolegar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,11]]},"reference":[{"key":"10172_CR1","doi-asserted-by":"publisher","unstructured":"Almeida, J.: Finite semigroups and universal algebra. World Scientific, Singapore (1995). https:\/\/doi.org\/10.1142\/2481","DOI":"10.1142\/2481"},{"key":"10172_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(85)90162-8","volume":"40","author":"W Bucher","year":"1985","unstructured":"Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. Theor. Comput. Sci. 40, 131\u2013148 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90162-8","journal-title":"Theor. Comput. Sci."},{"key":"10172_CR3","doi-asserted-by":"publisher","unstructured":"D\u2019Alessandro, F., Varricchio, S.: Well quasi-orders in formal language theory. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 84\u201395. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-85780-8_6","DOI":"10.1007\/978-3-540-85780-8_6"},{"key":"10172_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59849-4","author":"A de Luca","year":"1999","unstructured":"de Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Springer (1999). https:\/\/doi.org\/10.1007\/978-3-642-59849-4","journal-title":"Springer"},{"key":"10172_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(82)90124-4","volume":"27","author":"A Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theor. Comput. Sci. 27, 311\u2013332 (1983). https:\/\/doi.org\/10.1016\/0304-3975(82)90124-4","journal-title":"Theor. Comput. Sci."},{"key":"10172_CR6","doi-asserted-by":"publisher","unstructured":"Gehrke, M., Grigorieff, S., Pin, J.-\u00c9.: Duality and equational theory of regular languages. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol 5126, pp. 246\u2013257. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_21","DOI":"10.1007\/978-3-540-70583-3_21"},{"issue":"1","key":"10172_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"s3\u20132","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. s3\u20132(1), 326\u2013336 (1952). https:\/\/doi.org\/10.1112\/plms\/s3-2.1.326","journal-title":"Proc. Lond. Math. Soc."},{"key":"10172_CR8","unstructured":"Howie, J.M.: An Introduction to Semigroup Theory. Academic Press (1976)"},{"key":"10172_CR9","doi-asserted-by":"publisher","unstructured":"Kl\u00edma, O., Kolegar, J.: Well Quasi-Orders Arising from Finite Ordered Semigroups. In: Diekert, V., Volkov, M. (eds.) DLT 2022.LNCS, vol. 13257, pp. 201\u2013212. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-05578-2_16","DOI":"10.1007\/978-3-031-05578-2_16"},{"issue":"3","key":"10172_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0097-3165(72)90063-5","volume":"13","author":"JB Kruskal","year":"1972","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Comb. Theory, Ser. A 13(3), 297\u2013305 (1972). https:\/\/doi.org\/10.1016\/0097-3165(72)90063-5","journal-title":"J. Comb. Theory, Ser. A"},{"key":"10172_CR11","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.tcs.2005.09.018","volume":"348","author":"M Kunc","year":"2005","unstructured":"Kunc, M.: Regular solutions of language inequalities and well quasi-orders. Theor. Comput. Sci. 348, 277\u2013293 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.018","journal-title":"Theor. Comput. Sci."},{"key":"10172_CR12","doi-asserted-by":"publisher","unstructured":"Kunc, M., Okhotin, A.: Language equations. Handbook of Automata Theory. European Mathematical Society. 765\u2013799 (2021). https:\/\/doi.org\/10.4171\/Automata-1\/21","DOI":"10.4171\/Automata-1\/21"},{"key":"10172_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J-\u00c9 Pin","year":"1986","unstructured":"Pin, J.-\u00c9.: Varieties of Formal Languages. Foundations of computer science, North Oxford Academic (1986)"},{"key":"10172_CR14","doi-asserted-by":"publisher","unstructured":"Pin, J.-\u00c9.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. vol. 1, pp. 679\u2013746. Springer (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_10","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"10172_CR15","doi-asserted-by":"publisher","unstructured":"Pin, J.-\u00c9.: How to prove that a\u00a0language is regular or star-free? In: Leporati, A., Mart\u00edn-Vide, C., Shapira, D., Zandron, C. (eds.) LATA 2020. LNCS, vol. 12038, pp. 68\u201388. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-40608-0_5","DOI":"10.1007\/978-3-030-40608-0_5"},{"key":"10172_CR16","doi-asserted-by":"publisher","unstructured":"Pin, J.-\u00c9.: Finite automata. In: Handbook of automata theory. Vol. I. Theoretical foundations (J.-\u00c9. Pin ed.). European Mathematical Society. 3\u201338 (2021) https:\/\/doi.org\/10.4171\/Automata-1\/1","DOI":"10.4171\/Automata-1\/1"},{"issue":"1","key":"10172_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02007558","volume":"25","author":"K Sch\u00fctte","year":"1985","unstructured":"Sch\u00fctte, K., Simpson, S.G.: Ein in der reinen zahlentheorie unbeweisbarer satz \u00fcber endliche folgen von nat\u00fcrlichen zahlen. Arch. Math. Log. 25(1), 75\u201389 (1985). https:\/\/doi.org\/10.1007\/BF02007558","journal-title":"Arch. Math. Log."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10172-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10172-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10172-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T02:03:59Z","timestamp":1718935439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10172-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,11]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10172"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10172-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,4,11]]},"assertion":[{"value":"7 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}