Showing 1 - 2 of 2 Items
Thompson's group F is 1-counter graph automatic
Date: 2016-05-01
Creator: Murray Elder, Jennifer Taback
Access: Open access
- 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.
Tree-based language complexity of Thompson's group F
Date: 2015-11-01
Creator: Jennifer Taback, Sharif Younes
Access: Open access
- The definition of graph automatic groups by Kharlampovich, Khoussainov and Miasnikov and its extension to C-graph automatic by Elder and the first author raise the question of whether Thompson's group F is graph automatic. We define a language of normal forms based on the combinatorial "caret types", which arise when elements of F are considered as pairs of finite rooted binary trees. The language is accepted by a finite state machine with two counters, and forms the basis of a 3-counter graph automatic structure for the group.