Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Complexity of languages of geodesicsGeometry/Topology
|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.