Generalizations of the Muller-Schupp theorem and tree-like inverse graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914770641223680 |
|---|---|
| author | Rodaro, Emanuele |
| author_facet | Rodaro, Emanuele |
| contents | We extend the characterization of context-free groups of Muller and Schupp in two ways. We first show that for a quasi-transitive inverse graph $Γ$, being quasi-isometric to a tree, or context-free (finitely many end-cones types), or having the automorphism group $Aut(Γ)$ that is virtually free, are all equivalent conditions. Furthermore, we add to the previous equivalences a group theoretic analog to the representation theorem of Chomsky-Schützenberger that is fundamental in solving a weaker version of a conjecture of T. Brough which also extends Muller and Schupp' result to the class of groups that are virtually finitely generated subgroups of direct product of free groups. We show that such groups are precisely those whose word problem is the intersection of a finite number of languages accepted by quasi-transitive, tree-like inverse graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06664 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalizations of the Muller-Schupp theorem and tree-like inverse graphs Rodaro, Emanuele Group Theory Formal Languages and Automata Theory Combinatorics 20F65, 05C75, 20F10, 68Q70, 20M18, 57M10 We extend the characterization of context-free groups of Muller and Schupp in two ways. We first show that for a quasi-transitive inverse graph $Γ$, being quasi-isometric to a tree, or context-free (finitely many end-cones types), or having the automorphism group $Aut(Γ)$ that is virtually free, are all equivalent conditions. Furthermore, we add to the previous equivalences a group theoretic analog to the representation theorem of Chomsky-Schützenberger that is fundamental in solving a weaker version of a conjecture of T. Brough which also extends Muller and Schupp' result to the class of groups that are virtually finitely generated subgroups of direct product of free groups. We show that such groups are precisely those whose word problem is the intersection of a finite number of languages accepted by quasi-transitive, tree-like inverse graphs. |
| title | Generalizations of the Muller-Schupp theorem and tree-like inverse graphs |
| topic | Group Theory Formal Languages and Automata Theory Combinatorics 20F65, 05C75, 20F10, 68Q70, 20M18, 57M10 |
| url | https://arxiv.org/abs/2302.06664 |