All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 133

Showing per page

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 Hajós type result on factoring finite abelian groups by subsets. II

Keresztély Corrádi, Sándor Szabó (2010)

Commentationes Mathematicae Universitatis Carolinae

It is proved that if a finite abelian group is factored into a direct product of lacunary cyclic subsets, then at least one of the factors must be periodic. This result generalizes Hajós's factorization theorem.

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 21 – 40 of 133