اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConnected reversible Mealy automata of prime size cannot generate infinite Burnside groups
158
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most~3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.
قيم البحث
اقرأ أيضاً
Antonenko and Russyev independently have shown that any Mealy automaton with no cycles with exit--that is, where every cycle in the underlying directed graph is a sink component--generates a fi- nite (semi)group, regardless of the choice of the produ
ction functions. Antonenko has proved that this constitutes a characterization in the non-invertible case and asked for the invertible case, which is proved in this paper.
In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability re
sult of [1-3] for the emptiness problem of weakly synchronizing language is incorrect.
A group $Gamma$ is said to be periodic if for any $g$ in $Gamma$ there is a positive integer $n$ with $g^n=id$. We first prove that a finitely generated periodic group acting on the 2-sphere $SS^2$ by $C^1$-diffeomorphisms with a finite orbit, is f
inite and conjugate to a subgroup of $mathrm{O}(3,R)$ and we use it for proving that a finitely generated periodic group of spherical diffeomorphisms with even bounded orders is finite. Finally, we show that a finitely generated periodic group of homeomorphisms of any orientable compact surface other than the 2-sphere or the 2-torus (which is the purpose of a previous paper of the authors) is finite.
It was conjectured by v{C}erny in 1964 that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. In this paper, we investigate the ro
le of the alphabet size. For each possible alphabet size, we count DFAs on $n le 6$ states which synchronize in $(n-1)^2 - e$ steps, for all $e < 2lceil n/2 rceil$. Furthermore, we give constructions of automata with any number of states, and $3$, $4$, or $5$ symbols, which synchronize slowly, namely in $n^2 - 3n + O(1)$ steps. In addition, our results prove v{C}ernys conjecture for $n le 6$. Our computation has led to $27$ DFAs on $3$, $4$, $5$ or $6$ states, which synchronize in $(n-1)^2$ steps, but do not belong to v{C}ernys sequence. Of these $27$ DFAs, $19$ are new, and the remaining $8$ which were already known are exactly the emph{minimal} ones: they will not synchronize any more after removing a symbol. So the $19$ new DFAs are extensions of automata which were already known, including the v{C}erny automaton on $3$ states. But for $n > 3$, we prove that the v{C}erny automaton on $n$ states does not admit non-trivial extensions with the same smallest synchronizing word length $(n-1)^2$.
A group $G$ is said to be periodic if for any $gin G$ there exists a positive integer $n$ with $g^n=id$. We prove that a finitely generated periodic group of homeomorphisms on the 2-torus that preserves a measure $mu$ is finite. Moreover if the group
consists in homeomorphisms isotopic to the identity, then it is abelian and acts freely on $mathbb{T}^2$. In the Appendix, we show that every finitely generated 2-group of toral homeomorphisms is finite.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
