Semigroups arising from asynchronous automata.

DOI10.4171/GGD/222zbMATH Open1326.20063arXiv1011.2457OpenAlexW2964278487MaRDI QIDQ2016100FDOQ2016100

Authors: David McCune 

Publication date: 19 June 2014

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

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.

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automaton semigroups
• Automata, dynamical systems, and groups
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• Title not available (Why is that?)
• Title not available (Why is that?)
• Self-similarity and branching in group theory.
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Automata with restricted memory and shift endomorphisms
• Geometric properties and asynchronously automatic semigroups.
• Title not available (Why is that?)
• 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.
• Title not available (Why is that?)

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)