| Issue |
RAIRO-Theor. Inf. Appl.
Volume 56, 2022
|
|
|---|---|---|
| Article Number | 7 | |
| Number of page(s) | 13 | |
| DOI | https://doi.org/10.1051/ita/2022006 | |
| Published online | 01 July 2022 | |
Automatic sequences of rank two*
1
Department of Pure Mathematics, University of Waterloo, Waterloo, ON N2L 3G1, Canada
2
School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
* Corresponding author: shallit@uwaterloo.ca
Received:
13
August
2021
Accepted:
15
February
2022
Given a right-infinite word x over a finite alphabet A, the rank of x is the size of the smallest set S of words over A such that x can be realized as an infinite concatenation of words in S. We show that the property of having rank two is decidable for the class of k-automatic words for each integer k ≥ 2.
Mathematics Subject Classification: 68R15 / 11B85
Key words: Combinatorics on words / automatic sequence / primitive word / rank two
© The authors. Published by EDP Sciences, 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.