Some decidable congruences of free monoids

Jaroslav Ježek

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 \geq 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 \geq 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} \dots 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} = \dots = t_{m - 1}$ or $t_{1} > max {t_{2}, \dots, 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...

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.

*-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) \leq 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...

Theories of orders on the set of words

Dietrich Kuske (2006)

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

Similarity:

It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of...