On a class of poly-context-free groups generated by automata

This paper deals with graph automaton groups associated with trees and some generalizations. We start by showing some algebraic properties of tree automaton groups. Then we characterize the associated semigroup, proving that it is isomorphic to the partially commutative monoid associated with the co...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algebra 2023-07, Vol.626, p.135-162
Main Authors: Cavaleri, Matteo, D'Angeli, Daniele, Donno, Alfredo, Rodaro, Emanuele
Format: Article
Language:English
Subjects:
Dual automaton
Poly-context-free group
Reducible automaton
Tree automaton group
Tree automaton semigroup
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper deals with graph automaton groups associated with trees and some generalizations. We start by showing some algebraic properties of tree automaton groups. Then we characterize the associated semigroup, proving that it is isomorphic to the partially commutative monoid associated with the complement of the line graph of the defining tree. After that, we generalize these groups by introducing the quite broad class of reducible automaton groups, which lies in the class of contracting automaton groups without singular points. We give a general structure theorem that shows that all reducible automaton groups are direct limits of poly-context-free groups which are virtually subgroups of the direct product of free groups; notice that this result partially supports a conjecture by T. Brough. Moreover, we prove that tree automaton groups with at least two generators are not finitely presented and they are amenable groups, which are direct limit of non-amenable groups.
ISSN:0021-8693
1090-266X
DOI:10.1016/j.jalgebra.2023.03.023