A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
k-Abelian Equivalence and Rationality
Tekijät: Julien Cassaigne, Karhumäki Juhani, Puzynina Svetlana, Whiteland Markus
Toimittaja: S. Brlek and C. Reutenauer
Konferenssin vakiintunut nimi: International Conference on Developments in Language Theory
Kustannuspaikka: Berlin
Julkaisuvuosi: 2016
Kokoomateoksen nimi: Developments in Language Theory, 20th International Conference, DLT 2016
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 9840
Aloitussivu: 77
Lopetussivu: 88
Sivujen määrä: 12
ISBN: 978-3-662-53131-0
eISBN: 978-3-662-53132-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-53132-7_7
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$. We study
some combinatorial properties of $k$-abelian equivalence classes. Our starting point is a
characterization of $k$-abelian equivalence by rewriting, so-called $k$-switching. We show that
the set of lexicographically least representatives of equivalence classes is a regular language.
From this we infer that the sequence of the numbers of equivalence classes is $N$-rational. We
also show that the set of words defining $k$-abelian singleton classes is regular.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
