Automaton semigroups: the two-state case.

DOI10.1007/s00224-014-9594-0zbMath1345.20074OpenAlexW2025688699MaRDI QIDQ290910

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

zbMATH Keywords

automaton semigroupsdecidability of finitenessdecidability of freenessMealy automataNerode equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

On groups generated by bi-reversible automata: the two-state case over a changing alphabet ⋮ An automaton group with undecidable order and Engel problems ⋮ On level-transitivity and exponential growth ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ Unnamed Item ⋮ On the existence of free subsemigroups in reversible automata semigroups

Uses Software

• GAP
• automata
• AutomGrp
• FR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• Automata generating free products of groups of order 2.
• On a series of finite automata defining free transformation groups.
• On transition functions of Mealy automata of finite growth.
• Automaton semigroups
• On Burnside's problem on periodic groups
• 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.
• 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 A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• 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
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum