Groups and semigroups defined by colorings of synchronizing automata

DOI10.1142/S0218196714500337zbMath1314.20028arXiv1310.5242OpenAlexW2039914484MaRDI QIDQ2934265

Emanuele Rodaro, Daniele D'Angeli

Publication date: 12 December 2014

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

free semigroupswreath productsdeterministic finite automataautomata groupsMealy automataself-similar groupsbounded automatasynchronizing automataautomata semigroupsde Bruijn automata

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) 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

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 ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ A geometric approach to (semi)-groups defined by automata via dual transducers. ⋮ Fragile words and Cayley type transducers ⋮ Boundary dynamics for bireversible and for contracting automaton groups ⋮ The Lamplighter Group ℤ₃≀ℤ Generated by a Bireversible Automaton

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• Synchronizing automata with finitely many minimal synchronizing words
• On amenability of automata groups.
• Some topics in the dynamics of group actions on rooted trees.
• The road coloring problem
• Thurston equivalence of topological polynomials
• Volume entropy of hyperbolic buildings
• A condition for minimal interval exchange maps to be uniquely ergodic
• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• Resetting words for decidable automata
• Finitely Generated Ideal Languages and Synchronizing Automata
• STATE COMPLEXITY OF CODE OPERATORS
• Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• Finitely Generated Synchronizing Automata
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum