A geometric approach to (semi)-groups defined by automata via dual transducers.

DOI10.1007/S10711-014-0024-XMaRDI QIDQ2256271zbMATHOpenAlexFDO

Authors Daniele D'Angeli, Emanuele Rodaro

Publication date 19 February 2015

Published in Geometriae Dedicata (Search for Journal in Brave)

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

zbMATH Keywords

automata groupsSchreier graphsdynamics on the boundarysemigroups defined by automataStallings construction

Mathematics Subject Classification ID

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

Abstract: We give a geometric approach to groups defined by automata via the notion of enriched dual of an inverse transducer. Using this geometric correspondence we first provide some finiteness results, then we consider groups generated by the dual of Cayley type of machines. Lastly, we address the problem of the study of the action of these groups in the boundary. We show that examples of groups having essentially free actions without critical points lie in the class of groups defined by the transducers whose enriched dual generate a torsion-free semigroup. Finally, we provide necessary and sufficient conditions to have finite Schreier graphs on the boundary yielding to the decidability of the algorithmic problem of checking the existence of Schreier graphs on the boundary whose cardinalities are upper bounded by some fixed integer.

Recommendations

• Freeness of automaton groups vs boundary dynamics
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Cayley automatic groups and numerical characteristics of Turing transducers
• On a free group of transformations defined by an automaton.

Cites work

• scientific article; zbMATH DE number 3873585 (Why is no real title available?)
• scientific article; zbMATH DE number 4154724 (Why is no real title available?)
• scientific article; zbMATH DE number 53545 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• Automata generating free products of groups of order 2.
• Automata over a binary alphabet generating free groups of even rank.
• Ends of Schreier graphs and cut-points of limit spaces of self-similar groups
• Fixed points of endomorphisms of virtually free groups.
• Groups and semigroups defined by colorings of synchronizing automata.
• Groups defined by automata
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• On a free group of transformations defined by an automaton.
• On a series of finite automata defining free transformation groups.
• Schreier graphs of the Basilica group.
• Self-similar groups acting essentially freely on the boundary of the binary rooted tree
• Solution of the restricted Burnside problem for 2-groups
• Some topics in the dynamics of group actions on rooted trees.
• Stallings foldings and subgroups of free groups
• The spectra of lamplighter groups and Cayley machines.
• Totally nonfree actions and the infinite symmetric group

Cited in

(13)

• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• scientific article; zbMATH DE number 5946208 (Why is no real title available?)
• A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
• A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
• On bireversible Mealy automata and the Burnside problem
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
• Freeness of automaton groups vs boundary dynamics
• On the complexity of the word problem for automaton semigroups and automaton groups
• Automaton (semi)groups: Wang tilings and Schreier tries
• Boundary dynamics for bireversible and for contracting automaton groups
• On a class of poly-context-free groups generated by automata
• Fragile words and Cayley type transducers
• Infinite automaton semigroups and groups have infinite orbits

This page was built for publication: A geometric approach to (semi)-groups defined by automata via dual transducers.

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