Displaying similar documents to “Distance desert automata and the star height problem”

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

k-counting automata

Joël Allred, Ulrich Ultes-Nitsche (2012)

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

Similarity:

In this paper, we define -counting automata as recognizers for -languages, languages of infinite words. We prove that the class of -languages they recognize is a proper extension of the -regular languages. In addition we prove that languages recognized by -counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for -counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe...

-counting automata

Joël Allred, Ulrich Ultes-Nitsche (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we define -counting automata as recognizers for -languages, languages of infinite words. We prove that the class of -languages they recognize is a proper extension of the -regular languages. In addition we prove that languages recognized by -counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for -counting automata. However, we conjecture strongly...

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

Universality of Reversible Hexagonal Cellular Automata

Kenichi Morita, Maurice Margenstern, Katsunobu Imai (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We define a kind of cellular automaton called a hexagonal partitioned cellular automaton (HPCA), and study logical universality of a reversible HPCA. We give a specific 64-state reversible HPCA , and show that a Fredkin gate can be embedded in this cellular space. Since a Fredkin gate is known to be a universal logic element, logical universality of is concluded. Although the number of states of is greater than those of the previous...

Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier, Anne Lacroix, Narad Rampersad (2012)

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

Similarity:

We prove that the subsets of that are -recognizable for all abstract numeration systems are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier, Anne Lacroix, Narad Rampersad (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that the subsets of that are -recognizable for all abstract numeration systems are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.