Variations of the Morse-Hedlund theorem for k-abelian equivalence
In this paper we investigate local-to-global phenomena for a new family of complexity functions of infinite words indexed by k ≥ 0. Two finite words u and v are said to be k-abelian equivalent if for all words x of length less than or equal to k, the number of occurrences of x in u is equal to the n...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2017
|
| Sorozat: | Acta cybernetica
23 No. 1 |
| Kulcsszavak: | Matematika |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.23.1.2017.11 |
| Online Access: | http://acta.bibl.u-szeged.hu/50069 |
| LEADER | 01913nab a2200265 i 4500 | ||
|---|---|---|---|
| 001 | acta50069 | ||
| 005 | 20220620150536.0 | ||
| 008 | 180212s2017 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.23.1.2017.11 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Karhumäki Juhani | |
| 245 | 1 | 0 | |a Variations of the Morse-Hedlund theorem for k-abelian equivalence |h [elektronikus dokumentum] / |c Karhumäki Juhani |
| 260 | |c 2017 | ||
| 300 | |a 175-189 | ||
| 490 | 0 | |a Acta cybernetica |v 23 No. 1 | |
| 520 | 3 | |a In this paper we investigate local-to-global phenomena for a new family of complexity functions of infinite words indexed by k ≥ 0. Two finite words u and v are said to be k-abelian equivalent if for all words x of length less than or equal to k, the number of occurrences of x in u is equal to the number of occurrences of x in v. This defines a family of equivalence relations, bridging the gap between the usual notion of abelian equivalence (when k = 1) and equality (when k = ∞). Given an infinite word w, we consider the associated complexity function which counts the number of k-abelian equivalence classes of factors of w of length n. As a whole, these complexity functions have a number of common features: each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our paper. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Matematika | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Matematika | ||
| 700 | 0 | 1 | |a Saarela Aleksi |e aut |
| 700 | 0 | 1 | |a Zamboni Luca Q. |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/50069/1/actacyb_23_1_2017_11.pdf |z Dokumentum-elérés |