Paper published in a journal (Scientific congresses and symposiums)
Binomial Complexities and Parikh-Collinear Morphisms
Rigo, Michel; Stipulanti, Manon; Whiteland, Markus
2022In Lecture Notes in Computer Science, 13257, p. 251-262
Peer reviewed
 

Files


Full Text
paper-orbi.pdf
Author preprint (562.44 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Combinatorics on words; Factor complexity; Abelian complexity; Binomial complexity; iterates of Thue-Morse morphism
Abstract :
[en] Two words are k-binomially equivalent, if each word of length at most k occurs as a subword, or scattered factor, the same number of times in both words. The k-binomial complexity of an infinite word maps the natural n to the number of k-binomial equivalence classes represented by its factors of length n. Inspired by questions raised by Lejeune, we study the relationships between the k and (k+1)-binomial complexities; as well as the link with the usual factor complexity. We show that pure morphic words obtained by iterating a Parikh-collinear morphism, i.e. a morphism mapping all words to words with bounded abelian complexity, have bounded k-binomial complexity. In particular, we study the properties of the image of a Sturmian word by an iterate of the Thue-Morse morphism.
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 > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Binomial Complexities and Parikh-Collinear Morphisms
Publication date :
2022
Event name :
Developments in Language Theory
Event date :
du 9 mai 2022 au 13 mai 2022
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Heidelberg, Germany
Volume :
13257
Pages :
251-262
Peer reviewed :
Peer reviewed
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 13 January 2022

Statistics


Number of views
76 (12 by ULiège)
Number of downloads
58 (4 by ULiège)

Scopus citations®
 
5
Scopus citations®
without self-citations
2
OpenCitations
 
0

Bibliography


Similar publications



Contact ORBi