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
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
42 (5 by ULiège)
Number of downloads
13 (1 by ULiège)

Bibliography


Similar publications



Sorry the service is unavailable at the moment. Please try again later.
Contact ORBi