Standard

K-Abelian equivalence and rationality. / Cassaigne, Julien; Karhumäki, Juhani; Puzynina, Svetlana; Whiteland, Markus A.

In: Fundamenta Informaticae, Vol. 154, No. 1-4, 01.01.2017, p. 65-94.

Research output: Contribution to journal › Article › peer-review

Harvard

Cassaigne, J, Karhumäki, J, Puzynina, S & Whiteland, MA 2017, 'K-Abelian equivalence and rationality', Fundamenta Informaticae, vol. 154, no. 1-4, pp. 65-94. https://doi.org/10.3233/FI-2017-1553

APA

Cassaigne, J., Karhumäki, J., Puzynina, S., & Whiteland, M. A. (2017). K-Abelian equivalence and rationality. Fundamenta Informaticae, 154(1-4), 65-94. https://doi.org/10.3233/FI-2017-1553

Vancouver

Cassaigne J, Karhumäki J, Puzynina S, Whiteland MA. K-Abelian equivalence and rationality. Fundamenta Informaticae. 2017 Jan 1;154(1-4):65-94. https://doi.org/10.3233/FI-2017-1553

Author

Cassaigne, Julien ; Karhumäki, Juhani ; Puzynina, Svetlana ; Whiteland, Markus A. / K-Abelian equivalence and rationality. In: Fundamenta Informaticae. 2017 ; Vol. 154, No. 1-4. pp. 65-94.

BibTeX

@article{e7a9c18942284b5ab3d602b8f4172037,
title = "K-Abelian equivalence and rationality",
abstract = "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. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is -rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.",
keywords = "k-abelian equivalence, Rational sequences, Regular languages",
author = "Julien Cassaigne and Juhani Karhum{\"a}ki and Svetlana Puzynina and Whiteland, {Markus A.}",
year = "2017",
month = jan,
day = "1",
doi = "10.3233/FI-2017-1553",
language = "English",
volume = "154",
pages = "65--94",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1-4",

}

RIS

TY - JOUR

T1 - K-Abelian equivalence and rationality

AU - Cassaigne, Julien

AU - Karhumäki, Juhani

AU - Puzynina, Svetlana

AU - Whiteland, Markus A.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is -rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

AB - 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. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is -rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

KW - k-abelian equivalence

KW - Rational sequences

KW - Regular languages

UR - http://www.scopus.com/inward/record.url?scp=85027340559&partnerID=8YFLogxK

U2 - 10.3233/FI-2017-1553

DO - 10.3233/FI-2017-1553

M3 - Article

AN - SCOPUS:85027340559

VL - 154

SP - 65

EP - 94

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-4

ER -

ID: 35281155