Implementing Computations in Automaton (Semi)groups

DOI10.1007/978-3-642-31606-7_21zbMath1297.68145arXiv1310.4856OpenAlexW1535343962MaRDI QIDQ2914713

Jean Mairesse, Matthieu Picantin, Ines Klimann, Ali Akhavi, Sylvain Lombardy

Publication date: 20 September 2012

Published in: International Journal of Algebra and Computation, Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

growthfinitenessorderminimizationautomata groupsMealy automatadual automatafiniteness problemautomata semigroupsautomaton (semi)groupshelix graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Groups acting on trees (20E08)

Related Items (28)

On the complexity of the word problem for automaton semigroups and automaton groups ⋮ Automaton semigroups: the two-state case. ⋮ Freeness of automaton groups vs boundary dynamics ⋮ A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group ⋮ Numerical upper bounds on growth of automaton groups ⋮ Automorphisms of shift spaces and the Higman--Thompson groups: the one-sided case ⋮ On bireversible Mealy automata and the Burnside problem ⋮ Orbit automata as a new tool to attack the order problem in automaton groups ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ An automaton group with undecidable order and Engel problems ⋮ Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$ ⋮ On level-transitivity and exponential growth ⋮ A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group ⋮ Automaton (Semi)groups: Wang Tilings and Schreier Tries ⋮ Automaton semigroups: new constructions results and examples of non-automaton semigroups ⋮ A geometric approach to (semi)-groups defined by automata via dual transducers. ⋮ Algorithmic Decidability of Engel’s Property for Automaton Groups ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Generic properties in some classes of automaton groups ⋮ On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata ⋮ Automaton semigroup constructions. ⋮ Boundary dynamics for bireversible and for contracting automaton groups ⋮ Infinite automaton semigroups and groups have infinite orbits ⋮ The word and order problems for self-similar and automata groups ⋮ On the structure theory of partial automaton semigroups ⋮ A New Hierarchy for Automaton Semigroups

Cites Work

• Automata generating free products of groups of order 2.
• Automaton semigroups
• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• The conjugacy problem in automaton groups is not solvable.
• The smallest Mealy automaton of intermediate growth.
• Automata and square complexes.
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• CAYLEY AUTOMATON SEMIGROUPS
• ON THE CAYLEY SEMIGROUP OF A FINITE APERIODIC SEMIGROUP
• Groups acting on trees: From local to global structure

This page was built for publication: Implementing Computations in Automaton (Semi)groups