Karhumäki Juhani; Saarela Aleksi; Zamboni Luca Q.: Variations of the Morse-Hedlund theorem for k-abelian equivalence. In: Acta cybernetica, (23) 1. pp. 175-189. (2017)
Előnézet |
Cikk, tanulmány, mű
actacyb_23_1_2017_11.pdf Letöltés (389kB) | Előnézet |
Absztrakt (kivonat)
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.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2017 |
| Kötet: | 23 |
| Szám: | 1 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 175-189 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/50021/ |
| DOI: | 10.14232/actacyb.23.1.2017.11 |
| Kulcsszavak: | Matematika |
| Megjegyzések: | Bibliogr.: p. 188-189. és a lábjegyzetekben ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2018. feb. 12. 09:48 |
| Utolsó módosítás: | 2022. jún. 20. 15:05 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/50069 |
 |
Tétel nézet |
