Automaticity and Parikh-collinear Morphisms

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

Download

Paper published in a book (Scientific congresses and symposiums)

Automaticity and Parikh-collinear Morphisms

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

2023 • In Robert Merças; Anna E. Frid (Eds.) Words 2023

Peer reviewed

Permalink
https://hdl.handle.net/2268/302523

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

conf-version.pdf

Publisher postprint (2.58 MB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

combinatorics on words; Automatic sequences; Morphic words; Abelian complexity; Automated theorem proving; Walnut

Abstract :

[en] Parikh-collinear morphisms have recently received a lot of attention. They are defined by the property that the Parikh vectors of the images of letters are collinear. We first show that any fixed point of such a morphism is automatic. Consequently, we get under some mild technical assumption that the abelian complexity of a binary fixed point of a Parikh-collinear morphism is also automatic, and we discuss a generalization to arbitrary alphabets. Then, we consider the abelian complexity function of the fixed point of the Parikh-collinear morphism $0\mapsto 010011$, $1\mapsto 1001$. This $5$-automatic sequence is shown to be aperiodic, answering a question of Salo and Sportiello.

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 ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

Automaticity and Parikh-collinear Morphisms

Publication date :

2023

Event name :

Words 2023 14th international conference

Event place :

Umea, Sweden

Event date :

from 12 to 16 June 2023

Audience :

International

Main work title :

Words 2023

Editor :

Robert Merças

Anna E. Frid

Publisher :

Springer

ISBN/EAN :

978-3-031-33179-4

Collection name :

Lecture Notes in Computer Science, 13899

Pages :

247-260

Peer reviewed :

Peer reviewed

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]

Data Set :

https://link.springer.com/chapter/10.1007/978-3-031-33180-0_19

Available on ORBi :

since 11 May 2023

Statistics

Number of views

37 (6 by ULiège)

Number of downloads

54 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Allouche, J.P., Dekking, M., Queffélec, M.: Hidden automatic sequences. Comb. Theory 1(#20) (2021). https://doi.org/10.5070/C61055386
Allouche, J.P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003). https://doi.org/10.1017/CBO9780511546563
Allouche, J.-P., Shallit, J.: Automatic sequences are also non-uniformly morphic. In: Raigorodskii, A.M., Rassias, M.T. (eds.) Discrete Mathematics and Applications. SOIA, vol. 165, pp. 1–6. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55857-4_1
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), 191–238 (1994). http://projecteuclid.org/euclid.bbms/1103408547, journées Montoises (Mons, 1992)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66–92 (1960). https://doi.org/10.1002/malq.19600060105
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
Cassaigne, J., Nicolas, F.: Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin 10(suppl.), 661–676 (2003). http://projecteuclid.org/euclid.bbms/1074791324
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–920 (2011). https://doi.org/10.1142/S0129054111008489
Charlier, É., Leroy, J., Rigo, M.: Asymptotic properties of free monoid morphisms. Linear Algebra Appl. 500, 119–148 (2016). https://doi.org/10.1016/j.laa.2016.02. 030
Charlier, É., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci. 23(5), 1035–1066 (2012). https://doi.org/10.1142/S0129054112400448
Cobham, A.: Uniform tag sequences. Math. Syst. Theory 6, 164–192 (1972). https://doi.org/10.1007/BF01706087
Dekking, F.M.: The spectrum of dynamical systems arising from substitutions of constant length. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 41(3), 221–239 (1978). https://doi.org/10.1007/BF00534241
Durand, F., Leroy, J.: The constant of recognizability is computable for primitive morphisms. Journal of Integer Sequences 20(#17.4.5) (2017). https://cs.uwaterloo. ca/journals/JIS/VOL20/Leroy/leroy4.html
Erdős, P.: Some unsolved problems. Michigan Math. J. 4, 291–300 (1958). https://doi.org/10.1307/mmj/1028997963
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
Goč, D., Rampersad, N., Rigo, M., Salimov, P.: On the number of abelian bordered words (with an example of automatic theorem-proving). Internat. J. Found. Comput. Sci. 25(8), 1097–1110 (2014). https://doi.org/10.1142/S0129054114400267
Guo, Y.J., Lü, X.T., Wen, Z.X.: On the boundary sequence of an automatic sequence. Discrete Math. 345(1) (2022). https://doi.org/10.1016/j.disc. 2021.112632
Krawczyk, E., Müllner, C.: Automaticity of uniformly recurrent substitutive sequences (2023). https://doi.org/10.48550/arXiv.2111.13134
Mossé, B.: Reconnaissabilité des substitutions et complexité des suites automa-tiques. Bulletin de la Société Mathématique de France 124(2), 329–346 (1996). https://doi.org/10.24033/bsmf.2283
Mossé, B.: Puissance de mots et reconnaissabilité des points fixes d’une substitution. Theor. Comput. Sci. 99(2), 327–334 (1992). https://doi.org/10.1016/0304-3975(92)90357-L
Mousavi, H.: Automatic theorem proving in Walnut (2016). https://doi.org/10. 48550/ARXIV.1603.06017
Parreau, A., Rigo, M., Rowland, E., Vandomme, É.: A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences. Electron. J. Comb. 22(#P1.27) (2022). https://doi.org/10.37236/4478
Puzynina, S., Whiteland, M.A.: Abelian closures of infinite binary words. J. Comb. Theory Ser. A 185, 105524 (2022). https://doi.org/10.1016/j.jcta.2021.105524
Rigo, M.: Formal languages, automata and numeration systems. Vol. 1. ISTE, London; John Wiley & Sons Inc, Hoboken, NJ (2014), introduction to combinatorics on words, With a foreword by Valérie Bethé. https://doi.org/10.1002/9781119008200
Rigo, M.: Formal languages, automata and numeration systems. Vol. 2. Networks and Telecommunications Series, ISTE, London; John Wiley & Sons Inc, Hoboken, NJ (2014), applications to recognizability and decidability, With a foreword by Valérie Berthé. https://doi.org/10.1002/9781119042853
Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theor. Comput. Sci. 601, 47–57 (2015). https://doi. org/10.1016/j.tcs.2015.07.025
Rigo, M., Stipulanti, M., Whiteland, M.A.: Binomial complexities and Parikh-collinear morphisms. In: Diekert, V., Volkov, M.V. (eds.) Developments in Language Theory-26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13257, pp. 251– 262. Springer (2022). https://doi.org/10.1007/978-3-031-05578-2_20
Schaeffer, L.: Deciding Properties of Automatic Sequences. Master’s thesis, Univ. of Waterloo (2013). https://uwspace.uwaterloo.ca/handle/10012/7899
Shallit, J.: Abelian complexity and synchronization. INTEGERS: Electron. J. Comb. Number Theory (#A.36) (2021). http://math.colgate.edu/integers/v36/v36.pdf
Shallit, J.: The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series, Cambridge University Press (2022). https://doi.org/10.1017/9781108775267