Automata over a binary alphabet generating free groups of even rank.

DOI10.1142/S0218196711006194MaRDI QIDQ2996850zbMATH OpenFDO

Authors Benjamin Steinberg, Mariya Vorobets, Yaroslav Vorobets

Publication date 3 May 2011

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

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

zbMATH Keywords

free groupsfinite state automataself-similar groupsautomaton groupsfree products of cyclic groupsbireversible automata

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Groups acting on trees (20E08) Algebraic theory of languages and automata (68Q70)

Abstract: We construct automata over a binary alphabet with $2n$ states, $ngeq2$, whose states freely generate a free group of rank $2n$. Combined with previous work, this shows that a free group of every finite rank can be generated by finite automata over a binary alphabet. We also construct free products of cyclic groups of order two via such automata.

Recommendations

• Finite automaton actions of free groups
• On a free group of transformations defined by an automaton.
• Finite automata of polynomial growth do not generate a free group.
• On finite and Abelian groups generated by finite automata.
• scientific article; zbMATH DE number 1376768

Cites work

• Automata and square complexes.
• Cyclic renormalization and automorphism groups of rooted trees
• MONOIDS ACTING ON TREES: ELLIPTIC AND WREATH PRODUCTS AND THE HOLONOMY THEOREM FOR ARBITRARY MONOIDS WITH APPLICATIONS TO INFINITE GROUPS
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• On a free group of transformations defined by an automaton.
• The Generation of GL(n, Z) by Finite State Automata
• The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• The spectra of lamplighter groups and Cayley machines.

Cited in

(27)

• On a finite state representation of GL(n,Z)
• Automaton semigroup constructions.
• On the automaton complexity of wreath powers of non-Abelian finite simple groups.
• Representations of a free group of rank two by time-varying Mealy automata
• Freeness of automaton groups vs boundary dynamics
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• Generation of amalgamated free products of cyclic groups by finite automata over minimal alphabet
• Fragile words and Cayley type transducers
• Automaton semigroups: the two-state case.
• Catalan fragile words
• A geometric approach to (semi)-groups defined by automata via dual transducers.
• Automaton ranks of some self-similar groups.
• Automaton groups and complete square complexes
• Boundary dynamics for bireversible and for contracting automaton groups
• Finite automaton actions of free groups
• Free groups defined by finite $p$-automata
• Orbit automata as a new tool to attack the order problem in automaton groups
• Finite automata of polynomial growth do not generate a free group.
• On groups generated by bi-reversible automata: the two-state case over a changing alphabet
• The lamplighter group of rank two generated by a bireversible automaton
• Almost-automorphisms of trees, cloning systems and finiteness properties
• The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton
• Lamplighter groups, bireversible automata, and rational series over finite rings
• Bireversible automata generating lamplighter groups
• On a free group of transformations defined by an automaton.
• Finite automata over free groups
• Automaton semigroups: new constructions results and examples of non-automaton semigroups

This page was built for publication: Automata over a binary alphabet generating free groups of even rank.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996850)