Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Complementing the languages of unambigous automata
du 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