Unavoidable languages, cuts and innocent sets of words
L. Rosaz (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
L. Rosaz (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Štěpán Holub, Juha Kortelainen (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We prove that for each positive integer the finite commutative language possesses a test set of size at most Moreover, it is shown that each test set for has at least elements. The result is then generalized to commutative languages containing a word such that (i) and (ii) each symbol occurs at least twice in if it occurs at least twice in some word of : each such possesses a test set of size , where . The considerations rest on the analysis of some basic types...
Jérémie Chalopin, Pascal Ochem (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite -free word over a 5 letter alphabet with letter frequency and an infinite -free word over a 6 letter alphabet with letter frequency .
Ondřej Turek (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
A word defined over an alphabet is -balanced ( ) if for all pairs of factors , of of the same length and for all letters , the difference between the number of letters in and is less or equal to . In this paper we consider a ternary alphabet = {, , } and a class of substitutions defined by () = , () = , () = where 1. We prove that the fixed point of , formally written as (), is 3-balanced...
L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2009)
RAIRO - Theoretical Informatics and Applications
Similarity:
We study infinite words over an alphabet satisfying the property , where denotes the number of palindromic factors of length occurring in the language of . We study also infinite words satisfying a stronger property : every palindrome of has exactly one palindromic extension in . For binary words, the properties and coincide and these properties characterize Sturmian words, i.e., words with the complexity + 1 for any . In this paper, we focus on ternary infinite...
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...
Jacques Justin, Laurent Vuillon (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Currie, James D. (1995)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Ondřej Turek (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
In this paper we will deal with the balance properties of the infinite binary words associated to -integers when is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type , for , , , where . We will prove that such word is -balanced with . Finally, in the case that it is known [B. Adamczewski, (2002) 197–224] that the fixed point of the substitution , is not -balanced for any . We exhibit an infinite sequence of pairs...
Pascal Ochem (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern . These types, , , and , differ by the factor complexity and the asymptotic frequency of the letter 0. Type has polynomial factor complexity and letter frequency . Type has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type is obtained from type ...