ترغب بنشر مسار تعليمي؟ اضغط هنا

Thompsons group F is 1-counter graph automatic

156   0   0.0 ( 0 )
 نشر من قبل Jennifer Taback
 تاريخ النشر 2015
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

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 prese ntations 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})$.
181 - Gili Golan Polak 2020
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$-genera ted 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.
323 - Gili Golan , Mark Sapir 2015
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 employ s 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 $mathc al 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$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا