Evènement pour le groupe Séminaire Méthodes Formelles


Date 2018-04-03  11:00-12:00
TitreOn Rotating Q-Automata 
RésuméI present results on rotating Q-automata, which are (memoryless) automata with weights in Q that can read the input tape from left to right several times. We show that the series realized by valid rotating Q-automata are Q-Hadamard series (which are the closure of Q-rational series by pointwise inverse), and that every Q-Hadamard series can be realized by such an automaton. We prove that, although validity of rotating Q-automata is undecidable, the equivalence problem is decidable on rotating Q-automata. Finally, we prove that every valid two-way Q -automaton admits an equivalent rotating Q-automaton. The conversion, which is effective, implies the decidability of equivalence of two-way Q-automata. 
Lieu178 
OrateurLouis-Marie Dando 
Emailldando@u-bordeaux.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index