Page 1 Next

Displaying 1 – 20 of 28

Showing per page

Sequences of low arithmetical complexity

Sergey V. Avgustinovich, Julien Cassaigne, Anna E. Frid (2006)

RAIRO - Theoretical Informatics and Applications

Arithmetical complexity of a sequence is the number of words of length n that can be extracted from it according to arithmetic progressions. We study uniformly recurrent words of low arithmetical complexity and describe the family of such words having lowest complexity.

Signed Chip Firing Games and symmetric Sandpile Models on the cycles

Robert Cori, Thi Ha Duong Phan, Thi Thu Huong Tran (2013)

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

We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Some algorithms to compute the conjugates of episturmian morphisms

Gwenael Richomme (2003)

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

Episturmian morphisms generalize sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms L , and 𝔻 . Epistandard morphisms are the morphisms obtained without considering 𝔻 . In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism f over exchange morphisms and { L , 𝔻 } , we consider two problems: how to compute a decomposition of one conjugate of f ; how to compute a list of decompositions...

Some algorithms to compute the conjugates of Episturmian morphisms

Gwenael Richomme (2010)

RAIRO - Theoretical Informatics and Applications

Episturmian morphisms generalize Sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms L, and R. Epistandard morphisms are the morphisms obtained without considering R. In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism f over exchange morphisms and {L,R}, we consider two problems: how to compute a decomposition of one conjugate of f; how to compute a...

Some decision problems on integer matrices

Christian Choffrut, Juhani Karhumäki (2005)

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

Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension 3 , questions 1) and 3) are undecidable. For dimension 2 , they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...

Some decision problems on integer matrices

Christian Choffrut, Juhani Karhumäki (2010)

RAIRO - Theoretical Informatics and Applications

Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension 3, questions 1) and 3) are undecidable. For dimension 2, they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...

Squares and cubes in Sturmian sequences

Artūras Dubickas (2009)

RAIRO - Theoretical Informatics and Applications

We prove that every Sturmian word ω has infinitely many prefixes of the form UnVn3, where |Un| < 2.855|Vn| and limn→∞|Vn| = ∞. In passing, we give a very simple proof of the known fact that every Sturmian word begins in arbitrarily long squares.

Squares and overlaps in the Thue-Morse sequence and some variants

Shandy Brown, Narad Rampersad, Jeffrey Shallit, Troy Vasiga (2006)

RAIRO - Theoretical Informatics and Applications

We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of 2) contains an overlap.

Standard factors of Sturmian words

Gwénaël Richomme, Kalle Saari, Luca Q. Zamboni (2010)

RAIRO - Theoretical Informatics and Applications

Among the various ways to construct a characteristic Sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word c, some standard words occur that are not prefixes of c. We characterize all standard words occurring in any characteristic word (and so in any Sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.

Strongly automatic semigroups

Paul Mercat (2013)

Bulletin de la Société Mathématique de France

Dans cet article, nous introduisons la notion de semi-groupe fortement automatique, qui entraîne la notion d’automaticité des semi-groupes usuelle. On s’intéresse particulièrement aux semi-groupes de développements en base β , pour lesquels on obtient un critère de forte automaticité.

Study of irreducible balanced pairs for substitutive languages

Julien Bernat (2008)

RAIRO - Theoretical Informatics and Applications

Let be a language. A balanced pair (u,v) consists of two words u and v in which have the same number of occurrences of each letter. It is irreducible if the pairs of strict prefixes of u and v of the same length do not form balanced pairs. In this article, we are interested in computing the set of irreducible balanced pairs on several cases of languages. We make connections with the balanced pairs algorithm and discrete geometrical constructions related to substitutive languages. We characterize...

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)

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

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2011)

RAIRO - Theoretical Informatics and Applications

The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...

Currently displaying 1 – 20 of 28

Page 1 Next