اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Post Correspondence Problem and equalisers for certain free group and monoid morphisms
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A marked free monoid morphism is a morphism for which the image of each generator starts with a different letter, and immersions are the analogous maps in free groups. We show that the (simultaneous) PCP is decidable for immersions of free groups, and provide an algorithm to compute bases for the sets, called equalisers, on which the immersions take the same values. We also answer a question of Stallings about the rank of the equaliser. Analogous results are proven for marked morphisms of free monoids.
قيم البحث
اقرأ أيضاً
We develop the theory of fragile words by introducing the concept of eraser morphism and extending the concept to more general contexts such as (free) inverse monoids. We characterize the image of the eraser morphism in the free group case, and show
that it has decidable membership problem. We establish several algorithmic properties of the class of finite-${cal{J}}$-above (inverse) monoids. We prove that the image of the eraser morphism in the free inverse monoid case (and more generally, in the finite-${cal{J}}$-above case) has decidable membership problem, and relate its kernel to the free group fragile words.
In this paper we describe the profinite completion of the free solvable group on m generators of solvability length r>1. Then, we show that for m=r=2, the free metabelian group on two generators does not have the Congruence Subgroup Property.
The congruence subgroup problem for a finitely generated group $Gamma$ asks whether the map $hat{Autleft(Gammaright)}to Aut(hat{Gamma})$ is injective, or more generally, what is its kernel $Cleft(Gammaright)$? Here $hat{X}$ denotes the profinite comp
letion of $X$. It is well known that for finitely generated free abelian groups $Cleft(mathbb{Z}^{n}right)=left{ 1right}$ for every $ngeq3$, but $Cleft(mathbb{Z}^{2}right)=hat{F}_{omega}$, where $hat{F}_{omega}$ is the free profinite group on countably many generators. Considering $Phi_{n}$, the free metabelian group on $n$ generators, it was also proven that $Cleft(Phi_{2}right)=hat{F}_{omega}$ and $Cleft(Phi_{3}right)supseteqhat{F}_{omega}$. In this paper we prove that $Cleft(Phi_{n}right)$ for $ngeq4$ is abelian. So, while the dichotomy in the abelian case is between $n=2$ and $ngeq3$, in the metabelian case it is between $n=2,3$ and $ngeq4$.
The congruence subgroup problem for a finitely generated group $Gamma$ asks whether $widehat{Autleft(Gammaright)}to Aut(hat{Gamma})$ is injective, or more generally, what is its kernel $Cleft(Gammaright)$? Here $hat{X}$ denotes the profinite completi
on of $X$. In this paper we first give two new short proofs of two known results (for $Gamma=F_{2}$ and $Phi_{2}$) and a new result for $Gamma=Phi_{3}$: 1. $Cleft(F_{2}right)=left{ eright}$ when $F_{2}$ is the free group on two generators. 2. $Cleft(Phi_{2}right)=hat{F}_{omega}$ when $Phi_{n}$ is the free metabelian group on $n$ generators, and $hat{F}_{omega}$ is the free profinite group on $aleph_{0}$ generators. 3. $Cleft(Phi_{3}right)$ contains $hat{F}_{omega}$. Results 2. and 3. should be contrasted with an upcoming result of the first author showing that $Cleft(Phi_{n}right)$ is abelian for $ngeq4$.
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 soluti
ons 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
