Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Complexity of languages of geodesics


Speaker: Sean Cleary, CCNY, CUNY
Location: 3106 MSB
Start time: Wed, Jan 18 2006, 4:10PM

We address questions about recognizing geodesics 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 and Thompson's group F, and we show that the linguistic complexity can depend upon choice of generating set. This is joint work with Jennifer Taback and Murray Elder.