اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديد$mathcal C$-graph automatic groups
79
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 show that the higher rank lamplighter groups, or Diestel-Leader groups $Gamma_d(q)$ for $d geq 3$, are graph automatic. This introduces a new family of graph automatic groups which are not automatic.
We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has
poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n
^2log n)$ for the torsion-free case and NSPACE$(n^4log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Je.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounde
d. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $mathsf{NP}$. A yes answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $mathsf{PSPACE}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
