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


Date 2018-02-13  11:00-12:00
Titre Complementing the languages of unambigous automata 
RésuméUnambiguous non-deterministic finite automata have intermediate expressive power and succinctness between deterministic and non-deterministic automata. It has been conjectured that every unambiguous non-deterministic one-way finite automaton (1UFA) recognizing some language L can be converted into a 1UFA recognizing the complement of the original language L with polynomial increase in the number of states. A counterexample to this conjecture using only the 1-letter alphabet will be presented. 
Lieu178 
OrateurMichael Raskin 
Emailhttps://www.mccme.ru/~raskin/ 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index