Quasi-automatic groups are asynchronously automatic
arXiv:1906.01521 · doi:10.1016/j.tcs.2019.05.026
Abstract
A quasi-automatic semigroup is a finitely generated semigroup with a rational set of representatives such that the graph of right multiplication by any generator is a rational relation. A asynchronously automatic semigroup is a quasi-automatic semigroup for which these rational relations are also recognisable by two-tape automata. We show that when such a semigroup happens to be a group, the converse actually holds, meaning quasi-automatic groups are asynchronously automatic.
arXiv commentShort note, 5 pages, complementing a previous paper named Quasi-automatic Semigroups by Blanchette, Choffrut and Reutenauer