Quasi-automatic groups are asynchronously automatic

DOI10.1016/J.TCS.2019.05.026MaRDI QIDQ2326413zbMATH OpenOpenAlexFDO

Authors Benjamin Blanchette

Publication date 7 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.01521

zbMATH Keywords

asynchronously automatic groupscomputation complexityfinite automataquasi-automatic semigroupsrational transductions

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

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.

Recommendations

• Quasi-automatic semigroups
• Notions of automaticity in semigroups.
• Quasi-automatic semigroups
• Asynchronously automatic semigroups.
• Automatic semigroups

Cites work

• Automatic monoids and change of generators
• Automatic semigroups
• Automaticity and commutative semigroups
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• Quasi-automatic semigroups
• Transductions des langages de Chomsky

Cited in

(6)

• Semigroups arising from asynchronous automata.
• DETERMINISTIC AND NON-DETERMINISTIC ASYNCHRONOUS AUTOMATIC STRUCTURES
• ASYNCHRONOUS COMBINGS OF GROUPS
• Quasi-automatic semigroups
• Asynchronously automatic semigroups.
• On endomorphisms of automatic groups

This page was built for publication: Quasi-automatic groups are asynchronously automatic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2326413)