The word problem and growth of groups
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913269059420160 |
|---|---|
| author | Bondarenko, Ievgen |
| author_facet | Bondarenko, Ievgen |
| contents | Let $\mathrm{WP}_G$ denote the word problem in a finitely generated group $G$. We consider the complexity of $\mathrm{WP}_G$ with respect to standard deterministic Turing machines. Let $\mathrm{DTIME}_k(t(n))$ be the complexity class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_1(n\log n)$ if and only if $G$ is virtually nilpotent. We relate the complexity of the word problem and the growth of groups by showing that $\mathrm{WP}_G\not\in \mathrm{DTIME}_1(o(n\logγ(n)))$, where $γ(n)$ is the growth function of $G$. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_k(n)$ for strongly contracting automaton groups, $\mathrm{WP}_G\in\mathrm{DTIME}_k(n\log n)$ for groups generated by bounded automata, and $\mathrm{WP}_G\in\mathrm{DTIME}_k(n(\log n)^d)$ for groups generated by polynomial automata. In particular, for the Grigorchuk group, $\mathrm{WP}_G\not\in\mathrm{DTIME}_1(n^{1.7674})$ and $\mathrm{WP}_G\in\mathrm{DTIME}_1(n^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11148 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The word problem and growth of groups Bondarenko, Ievgen Group Theory Formal Languages and Automata Theory 20F10, 68Q70, 03D10, 20E08 Let $\mathrm{WP}_G$ denote the word problem in a finitely generated group $G$. We consider the complexity of $\mathrm{WP}_G$ with respect to standard deterministic Turing machines. Let $\mathrm{DTIME}_k(t(n))$ be the complexity class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_1(n\log n)$ if and only if $G$ is virtually nilpotent. We relate the complexity of the word problem and the growth of groups by showing that $\mathrm{WP}_G\not\in \mathrm{DTIME}_1(o(n\logγ(n)))$, where $γ(n)$ is the growth function of $G$. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_k(n)$ for strongly contracting automaton groups, $\mathrm{WP}_G\in\mathrm{DTIME}_k(n\log n)$ for groups generated by bounded automata, and $\mathrm{WP}_G\in\mathrm{DTIME}_k(n(\log n)^d)$ for groups generated by polynomial automata. In particular, for the Grigorchuk group, $\mathrm{WP}_G\not\in\mathrm{DTIME}_1(n^{1.7674})$ and $\mathrm{WP}_G\in\mathrm{DTIME}_1(n^2)$. |
| title | The word problem and growth of groups |
| topic | Group Theory Formal Languages and Automata Theory 20F10, 68Q70, 03D10, 20E08 |
| url | https://arxiv.org/abs/2403.11148 |