The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

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...