Currently displaying 1 – 17 of 17

Showing per page

Order by Relevance | Title | Year of publication

On the decidability of semigroup freeness

Julien CassaigneFrancois Nicolas — 2012

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

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

On the decidability of semigroup freeness

Julien CassaigneFrancois Nicolas — 2012

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In...

Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund

Julien CassaigneNataliya Chekhova — 2006

Annales de l’institut Fourier

La fonction de récurrence R ( n ) d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur n . Nous la calculons explicitement pour les suites d’Arnoux-Rauzy, définies par des conditions combinatoires qui en font une généralisation naturelle des suites sturmiennes. Puis nous répondons à une question de Morse et Hedlund (1940) en montrant que R ( n ) n ne peut avoir une limite finie pour aucune suite non ultimement périodique.

On the decidability of semigroup freeness

Julien CassaigneFrancois Nicolas — 2012

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset  ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In...

On conjugacy of languages

Julien CassaigneJuhani KarhumäkiJán Maňuch — 2001

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

We say that two languages X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a a two-element biprefix set Z , as well as all two-element sets which are conjugates.

Weak mixing and eigenvalues for Arnoux-Rauzy sequences

Julien CassaigneSébastien FerencziAli Messaoudi — 2008

Annales de l’institut Fourier

We define by simple conditions two wide subclasses of the so-called Arnoux-Rauzy systems; the elements of the first one share the property of (measure-theoretic) weak mixing, thus we generalize and improve a counter-example to the conjecture that these systems are codings of rotations; those of the second one have eigenvalues, which was known hitherto only for a very small set of examples.

Infinite periodic points of endomorphisms over special confluent rewriting systems

Julien CassaignePedro V. Silva — 2009

Annales de l’institut Fourier

We consider endomorphisms of a monoid defined by a special confluent rewriting system that admit a continuous extension to the completion given by reduced infinite words, and study from a dynamical viewpoint the nature of their infinite periodic points. For prefix-convergent endomorphisms and expanding endomorphisms, we determine the structure of the set of all infinite periodic points in terms of adherence values, bound the periods and show that all regular periodic points are attractors.

Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables

Julien CassaigneMarion Le Gonidec — 2010

Journal de Théorie des Nombres de Bordeaux

Nous étudions dans cet article deux familles d’ensembles d’entiers reconnaissables par des automates finis ou dénombrables. Les résultats concernant ces deux notions de reconnaissabilité qui sont présentés ici étendent de manière naturelle les résultats structurels usuels de la famille des ensembles k -reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.

On Conjugacy of Languages

Julien CassaigneJuhani KarhumäkiJán Maňuch — 2010

RAIRO - Theoretical Informatics and Applications

We say that two languages and are conjugates if they satisfy the for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.

Imbalances in Arnoux-Rauzy sequences

Julien CassaigneSébastien FerencziLuca Q. Zamboni — 2000

Annales de l'institut Fourier

In a 1982 paper Rauzy showed that the subshift ( X , T ) generated by the morphism 1 12 , 2 13 and 3 1 is a natural coding of a rotation on the two-dimensional torus 𝕋 2 , i.e., is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in 2 , each domain being translated by the same vector modulo a lattice. It was believed more generally that each sequence of block complexity 2 n + 1 satisfying a combinatorial criterion known as the condition of Arnoux and Rauzy codes the orbit of a point...

Page 1

Download Results (CSV)