Eprint first made available on ORBi (E-prints, working papers and research blog)
Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Rigo, Michel; Stipulanti, Manon; Whiteland, Markus
2024
 

Files


Full Text
sn-article.pdf
Author postprint (504.34 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Parikh-collinear morphism; recognizable morphism; automatic sequence; abelian complexity; substitution shift; automated theorem proving
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 assump- tions. 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 eras- ing, 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 ;  Université de Liège - ULiège > Mathematics
Language :
English
Title :
Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Publication date :
2024
Number of pages :
18
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Commentary :
Long version of [M. Rigo, M. Stipulanti, M. A. Whiteland, Automaticity and Parikh-collinear morphisms. In: Combinatorics on Words. Lecture Notes in Comput. Sci., vol. 13899, pp. 247–260. Springer, 2023. https://doi.org/10.1007/ 978-3-031-33180-0 19]
Available on ORBi :
since 28 May 2024

Statistics


Number of views
7 (4 by ULiège)
Number of downloads
2 (1 by ULiège)

Bibliography


Similar publications



Contact ORBi