Evènement pour le groupe Graphes et Logique

Date 2012-09-18  11:00-12:00
TitreComplexity of languages of geodesics 
RésuméWe address questions about recognizing geodesics in groups with simple automata, and consider both full languages of all geodesics from the identity and languages of unique normal form geodesics from the identity. We describe languages of geodesics which can be recognized by simple automata- finite state automata, pushdown automata and counter automata, and give some criteria which rule out the ability of some automata to recognize certain geodesic languages. The examples include wreath products examples and Thompson's group F, and we show that the linguistic complexity of languages of geodesics can depend upon choice of generating set. This is joint work with Jennifer Taback and Murray Elder. 
Lieusalle 178 
OrateurSean Cleary 
UrlCity College of New York 

Aucun document lié à cet événement.

Retour à l'index