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

DOI10.1007/S10711-014-0024-XzbMATH Open1322.20049arXiv1403.1722OpenAlexW3104270914MaRDI QIDQ2256271FDOQ2256271

Authors: Daniele D'Angeli, Emanuele Rodaro 

Publication date: 19 February 2015

Published in: Geometriae Dedicata (Search for Journal in Brave)

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.

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

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
• Implementing computations in automaton (semi)groups
• On a free group of transformations defined by an automaton.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Some topics in the dynamics of group actions on rooted trees.
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Title not available (Why is that?)
• 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
• Automata over a binary alphabet generating free groups of even rank.
• Automata generating free products of groups of order 2.
• On a series of finite automata defining free transformation groups.
• Title not available (Why is that?)
• Self-similar groups acting essentially freely on the boundary of the binary rooted tree
• Stallings foldings and subgroups of free groups
• Totally nonfree actions and infinite symmetric group
• Solution of the restricted Burnside problem for 2-groups
• Schreier graphs of the Basilica group.
• The spectra of lamplighter groups and Cayley machines.
• On a family of Schreier graphs of intermediate growth associated with a self-similar group
• Ends of Schreier graphs and cut-points of limit spaces of self-similar groups
• Fixed points of endomorphisms of virtually free groups.
• Title not available (Why is that?)
• Groups defined by automata

Cited In (13)

• Freeness of automaton groups vs boundary dynamics
• Infinite automaton semigroups and groups have infinite orbits
• A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group
• On the complexity of the word problem for automaton semigroups and automaton groups
• Automaton (Semi)groups: Wang Tilings and Schreier Tries
• Fragile words and Cayley type transducers
• A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group
• Boundary dynamics for bireversible and for contracting automaton groups
• Title not available (Why is that?)
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• On bireversible Mealy automata and the Burnside problem
• On a class of poly-context-free groups generated by automata
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata

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)