اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe complexity of solution sets to equations in hyperbolic groups
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in $mathsf{NSPACE}(n^2log n)$ for the
torsion-free case and $mathsf{NSPACE}(n^4log n)$ in the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Je.z, Diekert and others on $mathsf{PSPACE}$ algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.
We prove that for a one-ended hyperbolic graph $X$, the size of the quotient $X/G$ by a group $G$ acting freely and cocompactly bounds from below the number of simplices in an Eilenberg-MacLane space for $G$. We apply this theorem to show that one-en
ded hyperbolic cubulated groups (or more generally, one-ended hyperbolic groups with globally stable cylinders `a la Rips-Sela) cannot contain isomorphic finite-index subgroups of different indices.
We study conjugacy classes of solutions to systems of equations and inequations over torsion-free hyperbolic groups, and describe an algorithm to recognize whether or not there are finitely many conjugacy classes of solutions to such a system. The cl
ass of immutable subgroups of hyperbolic groups is introduced, which is fundamental to the study of equations in this context. We apply our results to enumerate the immutable subgroups of a torsion-free hyperbolic group.
Let $Gamma$ be a torsion-free hyperbolic group. We show that the set of solutions of any system of equations with one variable in $Gamma$ is a finite union of points and cosets of centralizers if and only if any two-generator subgroup of $Gamma$ is free.
Let $Gamma$ be a torsion-free hyperbolic group. We study $Gamma$--limit groups which, unlike the fundamental case in which $Gamma$ is free, may not be finitely presentable or geometrically tractable. We define model $Gamma$--limit groups, which alway
s have good geometric properties (in particular, they are always relatively hyperbolic). Given a strict resolution of an arbitrary $Gamma$--limit group $L$, we canonically construct a strict resolution of a model $Gamma$--limit group, which encodes all homomorphisms $Lto Gamma$ that factor through the given resolution. We propose this as the correct framework in which to study $Gamma$--limit groups algorithmically. We enumerate all $Gamma$--limit groups in this framework.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
