{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T06:40:14Z","timestamp":1734158414530,"version":"3.30.2"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"FRS-FNRS","award":["T.0196.23 (PDR), 1.C.104.24F., 1.B.466.21F."],"award-info":[{"award-number":["T.0196.23 (PDR), 1.C.104.24F., 1.B.466.21F."]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank\u00a01. In the conference DLT\u2013WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set.<\/jats:p>","DOI":"10.1007\/s00224-024-10197-5","type":"journal-article","created":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T07:01:59Z","timestamp":1728543719000},"page":"1622-1639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Automatic Abelian Complexities of Parikh-Collinear Fixed Points"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7463-8507","authenticated-orcid":false,"given":"Michel","family":"Rigo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2805-2465","authenticated-orcid":false,"given":"Manon","family":"Stipulanti","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6006-9902","authenticated-orcid":false,"given":"Markus A.","family":"Whiteland","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"key":"10197_CR1","doi-asserted-by":"publisher","unstructured":"Rigo, M., Stipulanti, M., Whiteland, M.A.: Automaticity and Parikh-collinear morphisms. In: Combinatorics on Words. Lecture Notes in Comput. Sci., vol. 13899, pp. 247\u2013260. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-33180-0_19","DOI":"10.1007\/978-3-031-33180-0_19"},{"key":"10197_CR2","doi-asserted-by":"publisher","unstructured":"Allouche, J.-P., Dekking, M., Queff\u00e9lec, M.: Hidden automatic sequences. Comb. Theory 1(20) (2021) https:\/\/doi.org\/10.5070\/C61055386","DOI":"10.5070\/C61055386"},{"key":"10197_CR3","unstructured":"Sloane, N.J.A., al.: The On-Line Encyclopedia of Integer Sequences. https:\/\/oeis.org"},{"issue":"4","key":"10197_CR4","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1142\/S0129054111008489","volume":"22","author":"J Cassaigne","year":"2011","unstructured":"Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. S. 22(4), 905\u2013920 (2011). https:\/\/doi.org\/10.1142\/S0129054111008489","journal-title":"Int. J. Found. Comput. S."},{"key":"10197_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2015.07.025","volume":"601","author":"M Rigo","year":"2015","unstructured":"Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theor. Comput. Sci. 601, 47\u201357 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.07.025","journal-title":"Theor. Comput. Sci."},{"key":"10197_CR6","first-page":"291","volume":"4","author":"P Erd\u0151s","year":"1958","unstructured":"Erd\u0151s, P.: Some unsolved problems. Michigan Math. J. 4, 291\u2013300 (1958)","journal-title":"Michigan Math. J."},{"key":"10197_CR7","doi-asserted-by":"publisher","unstructured":"Fici, G., Puzynina, S.: Abelian combinatorics on words: a survey. Comput. Sci. Rev. 47, 100532 (2023). https:\/\/doi.org\/10.1016\/j.cosrev.2022.100532","DOI":"10.1016\/j.cosrev.2022.100532"},{"key":"10197_CR8","doi-asserted-by":"publisher","first-page":"103932","DOI":"10.1016\/j.ejc.2024.103932","volume":"118","author":"M Rigo","year":"2024","unstructured":"Rigo, M., Stipulanti, M., Whiteland, M.A.: Characterizations of families of morphisms and words via binomial complexities. European J. Combin. 118, 103932 (2024). https:\/\/doi.org\/10.1016\/j.ejc.2024.103932","journal-title":"European J. Combin."},{"key":"10197_CR9","doi-asserted-by":"publisher","unstructured":"Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003). https:\/\/doi.org\/10.1017\/CBO9780511546563","DOI":"10.1017\/CBO9780511546563"},{"key":"10197_CR10","doi-asserted-by":"publisher","unstructured":"Shallit, J.: The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (2022). https:\/\/doi.org\/10.1017\/9781108775267","DOI":"10.1017\/9781108775267"},{"key":"10197_CR11","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF00534241","volume":"41","author":"FM Dekking","year":"1978","unstructured":"Dekking, F.M.: The spectrum of dynamical systems arising from substitutions of constant length. Z. Wahrscheinlichkeitstheor. Verw. Geb. 41, 221\u2013239 (1978). https:\/\/doi.org\/10.1007\/BF00534241","journal-title":"Z. Wahrscheinlichkeitstheor. Verw. Geb."},{"key":"10197_CR12","doi-asserted-by":"publisher","unstructured":"Allouche, J.-P., Shallit, J.: Automatic sequences are also non-uniformly morphic. In: Discrete Mathematics and Applications. Springer Optim. Appl., vol. 165, pp. 1\u20136. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-55857-4_1","DOI":"10.1007\/978-3-030-55857-4_1"},{"key":"10197_CR13","doi-asserted-by":"publisher","unstructured":"Krawczyk, E., M\u00fcllner, C.: Automaticity of uniformly recurrent substitutive sequences (2023). https:\/\/doi.org\/10.48550\/arXiv.2111.13134","DOI":"10.48550\/arXiv.2111.13134"},{"issue":"1\u20133","key":"10197_CR14","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0012-365X(97)00029-0","volume":"179","author":"F Durand","year":"1998","unstructured":"Durand, F.: A characterization of substitutive sequences using return words. Discrete Math. 179(1\u20133), 89\u2013101 (1998). https:\/\/doi.org\/10.1016\/S0012-365X(97)00029-0","journal-title":"Discrete Math."},{"issue":"4","key":"10197_CR15","first-page":"17","volume":"20","author":"F Durand","year":"2017","unstructured":"Durand, F., Leroy, J.: The constant of recognizability is computable for primitive morphisms. J. Integer Seq. 20(4), 17\u20134515 (2017)","journal-title":"J. Integer Seq."},{"issue":"4","key":"10197_CR16","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1017\/S0143385799133947","volume":"19","author":"F Durand","year":"1999","unstructured":"Durand, F., Host, B., Skau, C.: Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems 19(4), 953\u2013993 (1999). https:\/\/doi.org\/10.1017\/S0143385799133947","journal-title":"Ergodic Theory Dynam. Systems"},{"key":"10197_CR17","doi-asserted-by":"publisher","unstructured":"B\u00e9al, M.-P., Perrin, D., Restivo, A.: Recognizability of morphisms. Ergodic Theory Dyn. Syst. 1\u201325 (2023). https:\/\/doi.org\/10.1017\/etds.2022.109","DOI":"10.1017\/etds.2022.109"},{"issue":"2","key":"10197_CR18","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1051\/ita\/2013035","volume":"47","author":"F Durand","year":"2013","unstructured":"Durand, F.: Decidability of the HD0L ultimate periodicity problem. RAIRO Theor. Inform. Appl. 47(2), 201\u2013214 (2013). https:\/\/doi.org\/10.1051\/ita\/2013035","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"10197_CR19","unstructured":"Mitrofanov, I.: A proof for the decidability of HD0L ultimate periodicity. arXiv (2011). https:\/\/doi.org\/10.48550\/arXiv.1110.4780"},{"key":"10197_CR20","doi-asserted-by":"publisher","unstructured":"Mousavi, H.: Automatic Theorem Proving in Walnut. arXiv (2016). https:\/\/doi.org\/10.48550\/arXiv.1603.06017","DOI":"10.48550\/arXiv.1603.06017"},{"key":"10197_CR21","unstructured":"B\u00e9al, M.-P., Durand, F., Perrin, D.: Substitution shifts. manuscript (2024)"},{"key":"10197_CR22","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66\u201392 (1960). https:\/\/doi.org\/10.1002\/malq.19600060105","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"10197_CR23","doi-asserted-by":"publisher","unstructured":"B\u00e9al, M., Berth\u00e9, V., Perrin, D., Restivo, A.: A note on one-sided recognizable morphisms (2022). https:\/\/doi.org\/10.48550\/arXiv.2204.03892","DOI":"10.48550\/arXiv.2204.03892"},{"key":"10197_CR24","unstructured":"Shallit, J.: Abelian complexity and synchronization. INTEGERS: Electron. J. Comb. Number Theory 21(A.36) (2021)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10197-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10197-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10197-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T06:03:01Z","timestamp":1734156181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10197-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10197"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10197-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,10,10]]},"assertion":[{"value":"16 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval and Consent to Participate"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}