Evènement pour le groupe Graphes et Logique


Date 2009-03-17  11:00-12:00
TitreAutomatic structures: simple, difficult, rather unsolvable, and very unsolvable problems 
RésuméAutomatic structures are relational structures whose universe and relations are described by finite automata. Hence the first-order theory of every automatic structure is decidable (this idea goes back to Elgot, Buechi, and Rabin, its systematic study was initiated by Khoussainov and Nerode). Automatic structures are therefore recursive ones that, in some aspects, have much nicer properties. The talk will present natural problems and determine their algorithmic and recursion theoretic complexity. 
Lieu076 
OrateurDietrich Kuske 
Emailkuske@informatik.uni-leipzig.de 
UrlUniversité de Leipzig 



Aucun document lié à cet événement.

Retour
Retour à l'index