Displaying similar documents to “Some decidable congruences of free monoids”

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

Equations on partial words

Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis (2009)

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

Similarity:

It is well-known that some of the most basic properties of words, like the commutativity ( x y = y x ) and the conjugacy ( x z = z y ), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation x m y n = z p has only periodic solutions in a free monoid, that is, if x m y n = z p holds with integers m , n , p ≥ 2 , then there exists a word w such that x , y , z are powers of w . This result, which received a lot of attention, was first proved...

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

Binary equality words with two b ’s

Štěpán Holub, Jiří Sýkora (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Deciding whether a given word is an equality word of two nonperiodic morphisms is also known as the dual Post correspondence problem. Although the problem is decidable, there is no practical decision algorithm. Already in the binary case, the classification is a large project dating back to 1980s. In this paper we give a full classification of binary equality words in which one of the letters has two occurrences.

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.

On some properties of doubly-periodic words

Claudio Baiocchi (1997)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Similarity:

We study the functional equation: 1 ⁢ A ⁢ B ⁢ C = C ⁢ D ⁢ A where A , B , C and D are words over an alphabet A . In particular we prove a «structure result» for the inner factors B , D : for suitably chosen words X , Y , Z one has: 2 ⁢ B = X ⁢ Y ⁢ Z , D = Z ⁢ Y ⁢ X 2 ⁢ B = X ⁢ Y ⁢ Z , D = Z ⁢ Y ⁢ X 2 ⁢ B = X ⁢ Y ⁢ Z , D = Z ⁢ Y ⁢ X 2 ⁢ B = X ⁢ Y ⁢ Z , D = Z ⁢ Y ⁢ X . It is a generalization of the Lyndon-Schützenberger's Theorem (see [7]): if in (1) A or C is empty, formula (2) holds true with one among X , Y , Z which can be chosen empty.