Automatic Abelian Complexities of Parikh-Collinear Fixed Points

Abelian complexity; Automated theorem proving; Automatic sequence; Parikh-collinear morphism; Recognizable morphism; Substitution shift; Automatic sequences; Complexity functions; Fixed points; Morphisms; Theoretical Computer Science; Computational Theory and Mathematics

Abstract :

[en] 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 1. In the conference DLT–WORDS 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.

Disciplines :

Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Whiteland, Markus A. ; Department of Computer Science, Loughborough University, Loughborough, Leicestershire, United Kingdom

Language :

English

Title :

Automatic Abelian Complexities of Parikh-Collinear Fixed Points

Publication date :

2024

Journal title :

Theory of Computing Systems

ISSN :

1432-4350

eISSN :

1433-0490

Publisher :

Springer

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://link.springer.com/content/pdf/10.1007/s00224-024-10197-5.pdf

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Funding text :

M. Rigo is supported by the FNRS Research grant T.0196.23 (PDR). M. Stipulanti is an FNRS Research Associate supported by the Research grant 1.C.104.24F. Part of the work was performed while M. Whiteland was affiliated with University of Li\u00E8ge and supported by the FNRS Research grant 1.B.466.21F

Available on ORBi :

since 18 November 2024

Statistics

Number of views

4 (0 by ULiège)

Number of downloads

1 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

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–260. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33180-0_19
Allouche, J.-P., Dekking, M., Queffélec, M.: Hidden automatic sequences. Comb. Theory 1 (20) (2021) https://doi.org/10.5070/C61055386
Sloane, N.J.A., al.: The On-Line Encyclopedia of Integer Sequences. https://oeis.org
J. Cassaigne G. Richomme K. Saari L.Q. Zamboni Avoiding Abelian powers in binary words with bounded Abelian complexity Int. J. Found. Comput. S. 2011 22 4 905 920 2806895 10.1142/S0129054111008489
M. Rigo P. Salimov Another generalization of abelian equivalence: binomial complexity of infinite words Theor. Comput. Sci. 2015 601 47 57 3396335 10.1016/j.tcs.2015.07.025
P. Erdős Some unsolved problems Michigan Math. J. 1958 4 291 300 98702
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
M. Rigo M. Stipulanti M.A. Whiteland Characterizations of families of morphisms and words via binomial complexities European J. Combin. 2024 118 103932 4700146 10.1016/j.ejc.2024.103932
Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003). https://doi.org/10.1017/CBO9780511546563
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
F.M. Dekking The spectrum of dynamical systems arising from substitutions of constant length Z. Wahrscheinlichkeitstheor. Verw. Geb. 1978 41 221 239 461470 10.1007/BF00534241
Allouche, J.-P., Shallit, J.: Automatic sequences are also non-uniformly morphic. In: Discrete Mathematics and Applications. Springer Optim. Appl., vol. 165, pp. 1–6. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55857-4_1
Krawczyk, E., Müllner, C.: Automaticity of uniformly recurrent substitutive sequences (2023). https://doi.org/10.48550/arXiv.2111.13134
F. Durand A characterization of substitutive sequences using return words Discrete Math. 1998 179 1–3 89 101 1489074 10.1016/S0012-365X(97)00029-0
F. Durand J. Leroy The constant of recognizability is computable for primitive morphisms J. Integer Seq. 2017 20 4 17 4515 3622264
F. Durand B. Host C. Skau Substitutional dynamical systems, Bratteli diagrams and dimension groups Ergodic Theory Dynam. Systems 1999 19 4 953 993 1709427 10.1017/S0143385799133947
Béal, M.-P., Perrin, D., Restivo, A.: Recognizability of morphisms. Ergodic Theory Dyn. Syst. 1–25 (2023). https://doi.org/10.1017/etds.2022.109
F. Durand Decidability of the HD0L ultimate periodicity problem RAIRO Theor. Inform. Appl. 2013 47 2 201 214 3072319 10.1051/ita/2013035
Mitrofanov, I.: A proof for the decidability of HD0L ultimate periodicity. arXiv (2011). https://doi.org/10.48550/arXiv.1110.4780
Mousavi, H.: Automatic Theorem Proving in Walnut. arXiv (2016). https://doi.org/10.48550/arXiv.1603.06017
Béal, M.-P., Durand, F., Perrin, D.: Substitution shifts. manuscript (2024)
J.R. Büchi Weak second-order arithmetic and finite automata Z. Math. Logik Grundlagen Math. 1960 6 66 92 125010 10.1002/malq.19600060105
Béal, M., Berthé, V., Perrin, D., Restivo, A.: A note on one-sided recognizable morphisms (2022). https://doi.org/10.48550/arXiv.2204.03892
Shallit, J.: Abelian complexity and synchronization. INTEGERS: Electron. J. Comb. Number Theory 21 (A.36) (2021)