The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...