A4 Refereed article in a conference publication
Mapped Exponent and Asymptotic Critical Exponent of Words
Authors: Foster, Eva; Saarela, Aleksi; Vanhatalo, Aleksi
Editors: Ko, Sang-Ki; Manea, Florin
Conference name: International Conference on Developments in Language Theory
Publisher: Springer Nature Switzerland
Publication year: 2025
Journal: Lecture Notes in Computer Science
Book title : Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings
Volume: 16036
First page : 244
Last page: 260
ISBN: 978-3-032-01474-0
eISBN: 978-3-032-01475-7
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-032-01475-7_17
Web address : https://doi.org/10.1007/978-3-032-01475-7_17
Abstract
We study how much injective morphisms can increase the repetitiveness of a given word. This question has a few possible variations depending on the meaning of “repetitiveness”. We concentrate on fractional exponents of finite words and asymptotic critical exponents of infinite words. We characterize finite words that, when mapped by injective morphisms, can have arbitrarily high fractional exponent. For infinite words, alongside other results, we show that the asymptotic critical exponent grows at most by a constant factor (depending on the size of the alphabet) when mapped by an injective morphism. For both finite and infinite words, the binary case is better understood than the general case. This is a shortened version of the full paper.
We study how much injective morphisms can increase the repetitiveness of a given word. This question has a few possible variations depending on the meaning of “repetitiveness”. We concentrate on fractional exponents of finite words and asymptotic critical exponents of infinite words. We characterize finite words that, when mapped by injective morphisms, can have arbitrarily high fractional exponent. For infinite words, alongside other results, we show that the asymptotic critical exponent grows at most by a constant factor (depending on the size of the alphabet) when mapped by an injective morphism. For both finite and infinite words, the binary case is better understood than the general case. This is a shortened version of the full paper.
UTU Research Portal