Groups, Geometry, and Dynamics


Full-Text PDF (447 KB) | Metadata | Table of Contents | GGD summary
Volume 8, Issue 1, 2014, pp. 199–223
DOI: 10.4171/GGD/222

Published online: 2014-05-13

Semigroups arising from asynchronous automata

David McCune[1]

(1) William Jewell College, Liberty, USA

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.

Keywords: Automaton, asynchronous, semigroup

McCune David: Semigroups arising from asynchronous automata. Groups Geom. Dyn. 8 (2014), 199-223. doi: 10.4171/GGD/222