 |
 |
|
Evènement pour le groupe Graphes et Logique
| Date | 2009-03-17 11:00-12:00 |
| Titre | Automatic 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. |
| Lieu | 076 |
| Orateur | Dietrich Kuske |
| Email | kuske@informatik.uni-leipzig.de |
| Url | Université de Leipzig |
Aucun document lié à cet événement. RetourRetour à l'index
| |