On the complexity of the word problem of the R. Thompson group V
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911143034880000 |
|---|---|
| author | Birget, J. C. |
| author_facet | Birget, J. C. |
| contents | We analyze the proof by Lehnert and Schweitzer that the word problem of the Thompson group V is co-context-free, and we show that this word problem is the complement of the cyclic closure of a union of reverse deterministic context-free languages. The same is true for any finitely generated subgroup of V. For certain finite generating sets, this word problem is the complement of the cyclic closure of the union of four deterministic context-free languages. Therefore the word problem of V has quadratic time-complexity on a deterministic multitape Turing machine, and belongs to logDCFL. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_08592 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the complexity of the word problem of the R. Thompson group V Birget, J. C. Group Theory Computational Complexity We analyze the proof by Lehnert and Schweitzer that the word problem of the Thompson group V is co-context-free, and we show that this word problem is the complement of the cyclic closure of a union of reverse deterministic context-free languages. The same is true for any finitely generated subgroup of V. For certain finite generating sets, this word problem is the complement of the cyclic closure of the union of four deterministic context-free languages. Therefore the word problem of V has quadratic time-complexity on a deterministic multitape Turing machine, and belongs to logDCFL. |
| title | On the complexity of the word problem of the R. Thompson group V |
| topic | Group Theory Computational Complexity |
| url | https://arxiv.org/abs/2203.08592 |