Geodesic
Semigroups arising from asynchronous automata
David McCune1
1William Jewell College, Liberty, USA
Groups, geometry, and dynamics, Tome 8 (2014) no. 1, pp. 199-223

Voir la notice de l'article provenant de la source EMS Press

DOI

In this paper we study semigroups of transformations of free monoids (and transformations of the corresponding tree boundaries) that arise from asynchronous automata. We introduce a subclass of asynchronous automata that we call “expanding automata”. We show that every free partially commutative monoid is a synchronous automaton semigroup, and every free partially commutative semigroup is an expanding automaton semigroup. We show that undecidability arises in the actions of these semigroups on trees. In particular, in the class of asynchronous automata there is no algorithm which detects the presence of coincidence points and there is no algorithm which detects the presence of fixed points. We show that the classes of semigroups that arise from synchronous, expanding, and asynchronous automata are distinct classes of semigroups. We end the paper by covering some basic algebraic theory of these semigroups, with an emphasis on subgroups.
DOI : 10.4171/ggd/222
Classification : 20-XX, 00-XX
Mots-clés : Automaton, asynchronous, semigroup

David McCune  1

1 William Jewell College, Liberty, USA 
David McCune. Semigroups arising from asynchronous automata. Groups, geometry, and dynamics, Tome 8 (2014) no. 1, pp. 199-223. doi: 10.4171/ggd/222
@article{10_4171_ggd_222,
     author = {David McCune},
     title = {Semigroups arising from asynchronous automata},
     journal = {Groups, geometry, and dynamics},
     pages = {199--223},
     year = {2014},
     volume = {8},
     number = {1},
     doi = {10.4171/ggd/222},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/ggd/222/}
}
TY  - JOUR
AU  - David McCune
TI  - Semigroups arising from asynchronous automata
JO  - Groups, geometry, and dynamics
PY  - 2014
SP  - 199
EP  - 223
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4171/ggd/222/
DO  - 10.4171/ggd/222
ID  - 10_4171_ggd_222
ER  - 
%0 Journal Article
%A David McCune
%T Semigroups arising from asynchronous automata
%J Groups, geometry, and dynamics
%D 2014
%P 199-223
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4171/ggd/222/
%R 10.4171/ggd/222
%F 10_4171_ggd_222

Cité par Sources :