Semigroups arising from asynchronous automata.

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

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

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Automata with restricted memory and shift endomorphisms
• Title not available (Why is that?)
• Degrees of asynchronously automaton transformations
• Asynchronous sliding block maps
• DETERMINISTIC AND NON-DETERMINISTIC ASYNCHRONOUS AUTOMATIC STRUCTURES

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)