Evènement pour le groupe Graphes et Logique


Date 2011-03-29  11:00-12:00
TitreContext-free groups and locally finite graphs of finite tree-width 
RésuméA finitely generated group G is called context-free, if the set of words which represent the identity in G (over its generators) forms a context-free language. It is easy to see that this property is an invariant of the group and does not depend on the choice of generators. Muller and Schupp proved in 1983 that a group G is context-free if and only if it is virtually free, i.e., it has a free subgroup of finite index. Over the past decades many other characterizations of context-free groups have been established. For example, by an action on trees with finite node stabilizers (Dicks 1980, Dicks and Dunwoody 1989), decidability of the MSO theory of its Cayley graph (Kuske and Lohrey 2005). A related theorem of Kuske and Lohrey characterizes context-free groups by Cayley graphs of finite tree-width. Actually, we can state the following result: Let Γ be a connected and locally finite graph of finite tree-width. Let G be a group acting on Γ with finitely many orbits. Assume that each node-stabilizer is finite. Then G is virtually free. In my talk I will speak about a direct and combinatorial proof of this result which became possible due to a modification of a recent construction of Krön for a combinatorial proof of a structure theorem of Stallings (used in all other proofs for the theorem of Muller and Schupp). The talk is based on a joint work with Armin Weiß. 
Lieusalle 76 
OrateurVolker Diekert 
Emailvolker.diekert@fmi.uni-stuttgart.de 
UrlFMI, Stuttgart university 



Aucun document lié à cet événement.

Retour
Retour à l'index