Automaton semigroups: the two-state case.
DOI10.1007/S00224-014-9594-0zbMATH Open1345.20074OpenAlexW2025688699MaRDI QIDQ290910FDOQ290910
Authors: Ines Klimann 
Publication date: 3 June 2016
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9594-0
Recommendations
- The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
- scientific article; zbMATH DE number 2223017
- Implementing computations in automaton (semi)groups
- On torsion-free semigroups generated by invertible reversible Mealy automata
- Two-state Mealy automata of intermediate growth over a two-letter alphabet
automaton semigroupsdecidability of finitenessdecidability of freenessMealy automataNerode equivalence
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- Title not available (Why is that?)
- On Burnside's problem on periodic groups
- Title not available (Why is that?)
- ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
- On transition functions of Mealy automata of finite growth.
- Automaton semigroups
- Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
- The smallest Mealy automaton of intermediate growth.
- Automata and square complexes.
- On a free group of transformations defined by an automaton.
- Automata, dynamical systems, and groups
- Implementing computations in automaton (semi)groups
- Groups and semigroups defined by colorings of synchronizing automata.
- The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
- Automata over a binary alphabet generating free groups of even rank.
- On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
- Classification of groups generated by 3-state automata over a 2-letter alphabet
- CAYLEY AUTOMATON SEMIGROUPS
- ON THE CAYLEY SEMIGROUP OF A FINITE APERIODIC SEMIGROUP
- The finiteness problem for automaton semigroups is undecidable.
- Title not available (Why is that?)
- The lamplighter group as a group generated by a 2-state automaton, and its spectrum
- Automata generating free products of groups of order 2.
- On a series of finite automata defining free transformation groups.
Cited In (17)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An automaton group with undecidable order and Engel problems
- \((3,2)\)-semigroups generated by \((3,2)\)-automata.
- Two-state Mealy automata of intermediate growth over a two-letter alphabet
- Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet.
- Title not available (Why is that?)
- On groups generated by bi-reversible automata: the two-state case over a changing alphabet
- The smallest Mealy automaton of intermediate growth.
- On the existence of free subsemigroups in reversible automata semigroups
- Finite state quotients of free products of monogenic semigroups.
- Title not available (Why is that?)
- On level-transitivity and exponential growth
- Title not available (Why is that?)
- Permutive one-way cellular automata and the finiteness problem for automaton groups
- Title not available (Why is that?)
Uses Software
This page was built for publication: Automaton semigroups: the two-state case.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290910)
