Evènement pour le groupe Séminaire Méthodes Formelles


Date 2018-04-24  11:00-12:00
TitreThe isomorphism problem for virtually free group 
RésuméSince Muller and Schupp's result it is well-known that the finitely generated virtually free groups are precisely the context-free groups. The isomorphism problem for virtually free groups, has shown to be decidable by Kristic. In the special case that the input groups are either given as context-free grammars for their word problems or as so-called virtually free presentations, it is primitive recursive by the work of Sénizergues. In this talk I will present an elementary time solution for these two special cases. The proof is based on analyzing the structure trees assigned to the Cayley graphs of the input groups. By Bass-Serre theory this yields graphs of groups which can be tested for isomorphism as in Kristic's algorithm. The talk is based on joint work with Géraud Sénizergues and Volker Diekert. 
Lieu178 
OrateurArmin Weiß 
Emailhttp://www.fmi.uni-stuttgart.de/ti/team/weiss/ 
UrlStuttgart University 



Aucun document lié à cet événement.

Retour
Retour à l'index