Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConnected reversible Mealy automata of prime size cannot generate infinite Burnside groups
158
0
0.0
(
0
)
Added by
Ines Klimann
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 production 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 result 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 finite 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 role 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
