Regularity of k-Abelian equivalence classes of fixed cardinality

: Karhumäki Juhani, Whiteland Markus A.

: Hans-Joachim Böckenhauer, Dennis Komm, Walter Unger

Publisher: Springer Verlag

: 2018

: Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday

: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

: Lecture Notes in Computer Science

: 11011

: 49

: 62

: 978-3-319-98354-7

: 978-3-319-98355-4

: 0302-9743

DOI: https://doi.org/10.1007/978-3-319-98355-4_4

Two words u and v are said to be k-Abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. In this note we continue the analysis of k-Abelian equivalence classes. In particular, we show that, for any fixed integer r≥1" role="presentation">r≥1, the language of words representing equivalence classes of cardinality r is regular.