Context-free graphs and their transition groups
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912713797533696 |
|---|---|
| author | D'Angeli, Daniele Matucci, Francesco Perego, Davide Rodaro, Emanuele |
| author_facet | D'Angeli, Daniele Matucci, Francesco Perego, Davide Rodaro, Emanuele |
| contents | Starting from context-free inverse graphs, we introduce a new class of groups and study their structural properties. We establish closure properties, show that their co-word problems are context-free, analyze torsion elements, and realize them as subgroups of the asynchronous rational group. Context-freeness is preserved under a generalized free product of graphs, and using this construction we provide examples of groups that are not residually finite or not poly-context-free, making them relevant for testing the Lehnert and Brough conjectures. Moreover, we investigate how small local modifications of a graph affect the global structure of the transition group, showing that for locally quasi-transitive graphs with infinite orbits, the transition group decomposes into a highly structured quotient by a bounded torsion subgroup, showing strong global constraints induced by local graph properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13070 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Context-free graphs and their transition groups D'Angeli, Daniele Matucci, Francesco Perego, Davide Rodaro, Emanuele Group Theory Formal Languages and Automata Theory Combinatorics 20F65, 05C75, 20F10, 68Q70 Starting from context-free inverse graphs, we introduce a new class of groups and study their structural properties. We establish closure properties, show that their co-word problems are context-free, analyze torsion elements, and realize them as subgroups of the asynchronous rational group. Context-freeness is preserved under a generalized free product of graphs, and using this construction we provide examples of groups that are not residually finite or not poly-context-free, making them relevant for testing the Lehnert and Brough conjectures. Moreover, we investigate how small local modifications of a graph affect the global structure of the transition group, showing that for locally quasi-transitive graphs with infinite orbits, the transition group decomposes into a highly structured quotient by a bounded torsion subgroup, showing strong global constraints induced by local graph properties. |
| title | Context-free graphs and their transition groups |
| topic | Group Theory Formal Languages and Automata Theory Combinatorics 20F65, 05C75, 20F10, 68Q70 |
| url | https://arxiv.org/abs/2408.13070 |