Thompson's group F is 1-counter graph automatic

2015/01/18 by Murray Elder, Elder, Murray, Jennifer Taback +1
Computer Science · Mathematics · #20F65 #68Q45 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR) #cs.FL #math.GR #msc:20F65 #msc:68Q45

paper · pdf · doi:10.48550/arxiv.1501.04313

arxiv created 2015/01/18 · arxiv updated 2015/01/21

Abstract

It is not known whether Thompson's group F is automatic. With the recent extensions of the notion of an automatic group to graph automatic by Kharlampovich, Khoussainov and Miasnikov and then to C-graph automatic by the authors, a compelling question is whether F is graph automatic or C-graph automatic for an appropriate language class C. The extended definitions allow the use of a symbol alphabet for the normal form language, replacing the dependence on generating set. In this paper we construct a 1-counter graph automatic structure for F based on the standard infinite normal form for group elements.

Related

• Tree-based language complexity of Thompson's group F
• From automatic structures to automatic groups
• Restrictions on Potential Automatic Structures on Thompson's Group F
• The graph structure of graph groups that are subgroups of Thompson's group V
• Higher rank lamplighter groups are graph automatic