Semigroups arising from asynchronous automata.

DOI10.4171/GGD/222MaRDI QIDQ2016100zbMATH OpenOpenAlexFDO

Authors David McCune

Publication date 19 June 2014

Published in Groups, Geometry, and Dynamics (Search for Journal in Brave)

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

zbMATH Keywords

automaton semigroupsasynchronous automata

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic theory of languages and automata (68Q70) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: We introduce a new class of semigroups arising from a restricted class of asynchronous automata. We call these semigroups "expanding automaton semigroups." We show that the class of synchronous automaton semigroups is strictly contained in the class of expanding automaton semigroups, and that the class of expanding automaton semigroups is strictly contained in the class of asynchronous automaton semigroups. We investigate the dynamics of expanding automaton semigroups acting on regular rooted trees, and show that undecidability arises in these actions. We show that this class is not closed under taking normal ideal extensions, but the class of asynchronous automaton semigroups is closed under taking these extensions. We construct every free partially commutative monoid as a synchronous automaton semigroup.

Recommendations

• Asynchronously automatic semigroups.
• Quasi-automatic groups are asynchronously automatic
• Notes on finite asynchronous automata
• Quasi-automatic semigroups
• Automatic semigroups

Cites work

• scientific article; zbMATH DE number 3871636 (Why is no real title available?)
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 1762629 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• scientific article; zbMATH DE number 2223017 (Why is no real title available?)
• Automata, dynamical systems, and groups
• Automaton semigroups
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Self-similarity and branching in group theory.
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum

Cited in

(10)

• scientific article; zbMATH DE number 3988718 (Why is no real title available?)
• Automata with restricted memory and shift endomorphisms
• Geometric properties and asynchronously automatic semigroups.
• scientific article; zbMATH DE number 2062213 (Why is no real title available?)
• Automaton transformations and monadic theories of infinite sequences
• Degrees of asynchronously automaton transformations
• Asynchronous sliding block maps
• On asynchronous tree automata
• DETERMINISTIC AND NON-DETERMINISTIC ASYNCHRONOUS AUTOMATIC STRUCTURES
• Asynchronously automatic semigroups.

This page was built for publication: Semigroups arising from asynchronous automata.

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