Displaying similar documents to “Unambiguous erasing morphisms in free monoids”

A Hierarchy of Automatic -Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

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...

Submersions and effective descent of étale morphisms

David Rydh (2010)

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

Similarity:

Using the flatification by blow-up result of Raynaud and Gruson, we obtain new results for submersive and subtrusive morphisms. We show that universally subtrusive morphisms, and in particular universally open morphisms, are morphisms of descent for the fibered category of étale morphisms. Our results extend and supplement previous treatments on submersive morphisms by Grothendieck, Picavet and Voevodsky. Applications include the universality of geometric quotients and the elimination...

On the classes of languages accepted by limited context restarting automata

Friedrich Otto, Peter Černo, František Mráz (2014)

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

Similarity:

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word is accepted by such an automaton if, starting from the initial configuration that corresponds to input , the word is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context...

On biautomata

Ondřej Klíma, Libor Polák (2012)

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

Similarity:

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language its canonical biautomaton. This structure plays, among all biautomata recognizing the language , the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language . We expect that from the graph structure of this automaton one could decide the membership of a given language...

Undecidability of infinite post correspondence problem for instances of Size 9

Vesa Halava, Tero Harju (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

In the infinite Post Correspondence Problem an instance consists of two morphisms and , and the problem is to determine whether or not there exists an infinite word such that . This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini ( (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances...

On biautomata

Ondřej Klíma, Libor Polák (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language its canonical biautomaton. This structure plays, among all biautomata recognizing the language , the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language . We expect that from the graph structure of this automaton one could decide the membership of a given language...

Binary words avoiding the pattern AABBCABBA

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 1 2 . 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 ...

A remark on morphic sturmian words

J. Berstel, P. Séébold (1994)

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

Similarity: