The subword complexity of a class of infinite binary words
| dc.creator | Gheorghiciuc, Irina | |
| dc.date | 2005-12-13 | |
| dc.date.accessioned | 2026-07-07T06:55:07Z | |
| dc.date.available | 2026-07-07T06:55:07Z | |
| dc.description | Let $A_q$ be a $q$-letter alphabet and $w$ be a right infinite word on this alphabet. A subword of $w$ is a block of consecutive letters of $w$. The subword complexity function of $w$ assigns to each positive integer $n$ the number $f_w(n)$ of distinct subwords of length $n$ of $w$. The gap function of an infinite word over the binary alphabet $\{0,1 \}$ gives the distances between consecutive 1's in this word. In this paper we study infinite binary words whose gap function is injective or "almost injective". A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is strictly increasing is obtained. | |
| dc.description | 29 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0512256 | |
| dc.identifier | http://arxiv.org/abs/math/0512256 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/106178 | |
| dc.subject | Combinatorics | |
| dc.title | The subword complexity of a class of infinite binary words | |
| dc.type | text |