Displaying similar documents to “Abelian pattern avoidance in partial words”

Existence of an infinite ternary 64-abelian square-free word

Mari Huova (2014)

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

Similarity:

We consider a recently defined notion of of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length for a fixed natural number and the prefix of the word. We have shown earlier that over a ternary alphabet -abelian squares cannot be avoided in pure morphic words for any natural number . Nevertheless, computational experiments support the conjecture that even 3-abelian squares...

5-abelian cubes are avoidable on binary alphabets

Robert Mercaş, Aleksi Saarela (2014)

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

Similarity:

A -abelian cube is a word , where the factors , , and are either pairwise equal, or have the same multiplicities for every one of their factors of length at most . Previously it has been shown that -abelian cubes are avoidable over a binary alphabet for ≥ 8. Here it is proved that this holds for ≥ 5.

Finite repetition threshold for large alphabets

Golnaz Badkobeh, Maxime Crochemore, Michaël Rao (2014)

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

Similarity:

We investigate the finite repetition threshold for -letter alphabets, ≥ 4, that is the smallest number for which there exists an infinite -free word containing a finite number of -powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

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

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

Look and Say Fibonacci

Patrice Séébold (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The () derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, 1 1 2 3 3) = 2 1 1 2 2 3 (two , one , two ). We start the study of the behaviour of binary words generated by morphisms under the operator, focusing in particular on the Fibonacci word.