Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThompsons group F is 1-counter graph automatic
160
0
0.0
(
0
)
Added by
Jennifer Taback
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
It is not known whether Thompsons 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.
rate research
Read More
We produce a sequence of markings $S_k$ of Thompsons group $F$ within the space ${mathcal G}_n$ of all marked $n$-generator groups so that the sequence $(F,S_k)$ converges to the free group on $n$ generators, for $n geq 3$. In addition, we give presentations for the limits of some other natural (convergent) sequences of markings to consider on $F$ within ${mathcal G}_3$, including $(F,{x_0,x_1,x_n})$ and $(F,{x_0,x_1,x_0^n})$.
We prove that under two natural probabilistic models (studied by Cleary, Elder, Rechnitzer and Taback), the probability that a random pair of elements of Thompsons group $F$ generate the entire group is positive. We also prove that for any $k$-generated subgroup $H$ of $F$ which contains a natural copy of $F$, the probability of a random $(k+2)$-generated subgroup of $F$ coinciding with $H$ is positive.
We provide two ways to show that the R. Thompson group $F$ has maximal subgroups of infinite index which do not fix any number in the unit interval under the natural action of $F$ on $(0,1)$, thus solving a problem by D. Savchuk. The first way employs Jones subgroup of the R. Thompson group $F$ and leads to an explicit finitely generated example. The second way employs directed 2-complexes and 2-dimensional analogs of Stallings core graphs, and gives many implicit examples. We also show that $F$ has a decreasing sequence of finitely generated subgroups $F>H_1>H_2>...$ such that $cap H_i={1}$ and for every $i$ there exist only finitely many subgroups of $F$ containing $H_i$.
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.
We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov (arXiv:1107.3645) by replacing the regular languages in their definition with more powerful language classes. For a fixed language class $mathcal C$, we call the resulting groups $mathcal C$-graph automatic. We prove that the class of $mathcal C$-graph automatic groups is closed under change of generating set, direct and free product for certain classes $mathcal C$. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompsons groups $F,T$ and $V$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
