Page 1 Next

Displaying 1 – 20 of 408

Showing per page

5-abelian cubes are avoidable on binary alphabets

Robert Mercaş, Aleksi Saarela (2014)

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

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

A density version of the Carlson–Simpson theorem

Pandelis Dodos, Vassilis Kanellopoulos, Konstantinos Tyros (2014)

Journal of the European Mathematical Society

We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following. For every integer k 2 and every set A of words over k satisfying lim sup n | A [ k ] n | / k n > 0 there exist a word c over k and a sequence ( w n ) of left variable words over k such that the set c { c w 0 ( a 0 ) . . . w n ( a n ) : n and a 0 , . . . , a n [ k ] } is contained in A . While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

A finite word poset.

Erdős, Péter L., Sziklai, Péter, Torney, David C. (2001)

The Electronic Journal of Combinatorics [electronic only]

A general upper bound in extremal theory of sequences

Martin Klazar (1992)

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function f ( u , n ) which, for a given finite sequence u over k symbols, is defined as the maximum length m of a sequence v = a 1 a 2 . . . a m of integers such that 1) 1 a i n , 2) a i = a j , i j implies | i - j | k and 3) v contains no subsequence of the type u . We prove that f ( u , n ) is very near to be linear in n for any fixed u of length greater than 4, namely that f ( u , n ) = O ( n 2 O ( α ( n ) | u | - 4 ) ) . Here | u | is the length of u and α ( n ) is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

A generalization of the self-dual induction to every interval exchange transformation

Sébastien Ferenczi (2014)

Annales de l’institut Fourier

We generalize to all interval exchanges the induction algorithm defined by Ferenczi and Zamboni for a particular class. Each interval exchange corresponds to an infinite path in a graph whose vertices are certain unions of trees we call castle forests. We use it to describe those words obtained by coding trajectories and give an explicit representation of the system by Rokhlin towers. As an application, we build the first known example of a weakly mixing interval exchange outside the hyperelliptic...

A generator of morphisms for infinite words

Pascal Ochem (2006)

RAIRO - Theoretical Informatics and Applications

We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne's thesis are 2-avoidable. We also prove that there exist exponentially many 7 4 + -free ternary words and 7 5 + -free 4-ary words. Finally we give small morphisms for binary words containing only the squares 2, 12 and (01)² and for binary words avoiding...

A graph approach to computing nondeterminacy in substitutional dynamical systems

Toke M. Carlsen, Søren Eilers (2007)

RAIRO - Theoretical Informatics and Applications

We present an algorithm which for any aperiodic and primitive substitution outputs a finite representation of each special word in the shift space associated to that substitution, and determines when such representations are equivalent under orbit and shift tail equivalence. The algorithm has been implemented and applied in the study of certain new invariants for flow equivalence of substitutional dynamical systems.

A hierarchy for circular codes

Giuseppe Pirillo (2008)

RAIRO - Theoretical Informatics and Applications

We first prove an extremal property of the infinite Fibonacci* word f: the family of the palindromic prefixes {hn | n ≥ 6} of f is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

A Hierarchy of Automatic ω-Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

A length bound for binary equality words

Jana Hadravová (2011)

Commentationes Mathematicae Universitatis Carolinae

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 .

A little more about morphic Sturmian words

Isabelle Fagnot (2006)

RAIRO - Theoretical Informatics and Applications

Among Sturmian words, some of them are morphic, i.e. fixed point of a non-identical morphism on words. Berstel and Séébold (1993) have shown that if a characteristic Sturmian word is morphic, then it can be extended by the left with one or two letters in such a way that it remains morphic and Sturmian. Yasutomi (1997) has proved that these were the sole possible additions and that, if we cut the first letters of such a word, it didn't remain morphic. In this paper, we give an elementary and combinatorial...

A morphic approach to combinatorial games : the Tribonacci case

Eric Duchêne, Michel Rigo (2008)

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

We propose a variation of Wythoff’s game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

A morphic approach to combinatorial games: the Tribonacci case

Eric Duchêne, Michel Rigo (2007)

RAIRO - Theoretical Informatics and Applications

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

Currently displaying 1 – 20 of 408

Page 1 Next