Subsets of groups with context-free preimages
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914776178753536 |
|---|---|
| author | Levine, Alex |
| author_facet | Levine, Alex |
| contents | We study subsets $E$ of finitely generated groups where the set of all words over a given finite generating set that lie in $E$ forms a context-free language. We call these sets recognisably context-free. They are invariant of the choice of generating set and a theorem of Muller and Schupp fully classifies when the set $\{1\}$ can be recognisably context-free. We extend Muller and Schupp's result to show that a group $G$ admits a finite recognisably context-free subset if and only if $G$ is virtually free. We show that every conjugacy class of a group $G$ is recognisably context-free if and only if $G$ is virtually free. We conclude by showing that a coset is recognisably context-free if and only if the Schreier coset graph of the corresponding subgroup is quasi-isometric to a tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04191 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Subsets of groups with context-free preimages Levine, Alex Group Theory Formal Languages and Automata Theory 03D05, 20F10, 20F65, 68Q45 We study subsets $E$ of finitely generated groups where the set of all words over a given finite generating set that lie in $E$ forms a context-free language. We call these sets recognisably context-free. They are invariant of the choice of generating set and a theorem of Muller and Schupp fully classifies when the set $\{1\}$ can be recognisably context-free. We extend Muller and Schupp's result to show that a group $G$ admits a finite recognisably context-free subset if and only if $G$ is virtually free. We show that every conjugacy class of a group $G$ is recognisably context-free if and only if $G$ is virtually free. We conclude by showing that a coset is recognisably context-free if and only if the Schreier coset graph of the corresponding subgroup is quasi-isometric to a tree. |
| title | Subsets of groups with context-free preimages |
| topic | Group Theory Formal Languages and Automata Theory 03D05, 20F10, 20F65, 68Q45 |
| url | https://arxiv.org/abs/2312.04191 |