Displaying similar documents to “Equations on partial words”

On low-complexity bi-infinite words and their factors

Alex Heinis (2001)

Journal de théorie des nombres de Bordeaux

Similarity:

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness k if the number of different subwords of length n equals n + k for all n sufficiently large. The word is called k -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most k . In the present paper we give a complete description of the class of bi-infinite words of stiffness k and show that the number of subwords of length n from this class has...

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

For any finite word w on a finite alphabet, we consider the basic parameters R w and K w of w defined as follows: R w is the minimal natural number for which w has no right special factor of length R w and K w is the minimal natural number for which w has no repeated suffix of length K w . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the complexity of the infinite word u β associated with the Rényi expansion of 1 in an irrational base β > 1 . When β is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity ℂ ( n ) = n + 1 . For β such that d β ( 1 ) = t 1 t 2 ⋯ t m is finite we provide a simple description of the structure of special factors of the word u β . When t m = 1 we show that ℂ ( n ) = ( m - 1 ) n + 1 . In the cases when t 1 = t 2 = ⋯ = t m - 1 or t 1 > max { t 2 , ⋯ , t m - 1 } we show that the first difference of the complexity function ℂ ( n + 1 ) - ℂ ( n ) takes value in { m - 1 , m } for every n , and consequently...

A test-set for k -power-free binary morphisms

F. Wlazinski (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

A morphism f is k -power-free if and only if f ( w ) is k -power-free whenever w is a k -power-free word. A morphism f is k -power-free up to m if and only if f ( w ) is k -power-free whenever w is a k -power-free word of length at most m . Given an integer k ≥ 2 , we prove that a binary morphism is k -power-free if and only if it is k -power-free up to k 2 . This bound becomes linear for primitive morphisms: a binary primitive morphism is k -power-free if and only if it is k -power-free up to 2 k + 1 ...

A length bound for binary equality words

Jana Hadravová (2011)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let w be an equality word of two binary non-periodic morphisms g , h : { a , b } * → Δ * with unique overflows. It is known that if w contains at least 25 occurrences of each of the letters a and b , then it has to have one of the following special forms: up to the exchange of the letters a and b either w = ( a b ) i a , or w = a i b j with gcd ( i , j ) = 1 . We will generalize the result, justify this bound and prove that it can be lowered to nine occurrences of each of the letters a and b .

Periodicity problem of substitutions over ternary alphabets

Bo Tan, Zhi-Ying Wen (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper, we characterize the substitutions over a three-letter alphabet which generate a ultimately periodic sequence.

*-sturmian words and complexity

Izumi Nakashima, Jun-Ichi Tamura, Shin-Ichi Yasutomi (2003)

Journal de théorie des nombres de Bordeaux

Similarity:

We give analogs of the complexity p ( n ) and of Sturmian words which are called respectively the * -complexity p * ( n ) and * -Sturmian words. We show that the class of * -Sturmian words coincides with the class of words satisfying p * ( n ) ≤ n + 1 , and we determine the structure of * -Sturmian words. For a class of words satisfying p * ( n ) = n + 1 , we give a general formula and an upper bound for p ( n ) . Using this general formula, we give explicit formulae for p ( n ) for some words belonging to this class. In general, p ( n ) can take large...