Tree-based language complexity of Thompsons group F


Abstract in English

The definition of graph automatic groups by Kharlampovich, Khoussainov and Miasnikov and its extension to C-graph automatic by Murray Elder and the first author raise the question of whether Thompsons 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, which we show to be accepted by a finite state machine with 2 counters, and forms the basis of a 3-counter graph automatic structure for the group.

Download