Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.
É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.
É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.
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...
Mika Hirvensalo, Sebastian Seibert (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We show that the size of a automaton and the size of a complete, minimal automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction to , but here...