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. |
Lieu | 178 |
Orateur | Michael Raskin |
Email | https://www.mccme.ru/~raskin/ |
Url | LaBRI |
Aucun document lié à cet événement.
RetourRetour à l'index