Evènement pour le groupe Graphes et Logique


Date 2010-05-11  11:00-12:00
TitreThe Tree-Width of the Auxiliary Storage 
RésuméThe talk is about a generalization of various results on the decidability of emptiness for several restricted classes of sequential and distributed automata with auxiliary storage (stacks, queues) that have recently been proved. Our generalization relies on reducing emptiness of these automata to finite-state *graph automata* (without storage) defined on monadic second-order (MSO) definable graphs of bounded tree-width, where the graph structure encodes the mechanism provided by the auxiliary storage. Our results outline a uniform mechanism to derive emptiness algorithms for automata, explaining and simplifying several existing results, as well as proving new decidability theorems. 
LieuSalle 076 
OrateurGennaro Parlato 
UrlUIUC / Paris 7 



Aucun document lié à cet événement.

Retour
Retour à l'index