اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSolutions to twisted word equations and equations in virtually free groups
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or small enough) finite monoid, then our algorithms can be implemented in $mathsf{NSPACE}(n^2log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.
قيم البحث
اقرأ أيضاً
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 finitely generated virtually free groups are stable in permutations. As an application, we show that almost-periodic almost-automorphisms of labelled graphs are close to periodic automorphisms.
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.
We prove the pro-$p$ version of the Karras, Pietrowski, Solitar, Cohen and Scott result stating that a virtually free group acts on a tree with finite vertex stabilizers. If a virtually free pro-$p$ group $G$ has finite centralizes of all non-trivial
torsion elements more stronger statement is proved: $G$ embeds into a free pro-$p$ product of a free pro-$p$ group and finite $p$-group. The integral $p$-adic representation theory is used in the proof; it replaces the Stallings theory of ends in the pro-$p$ case.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
