The Word Problem for Finitary Automaton Groups
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917611003969536 |
|---|---|
| author | Kotowsky, Maximilian Wächter, Jan Philipp |
| author_facet | Kotowsky, Maximilian Wächter, Jan Philipp |
| contents | A finitary automaton group is a group generated by an invertible, deterministic finite-state letter-to-letter transducer whose only cycles are self-loops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is coNP-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we also show that the respective compressed word problem, where the state sequence is given as a straight-line program, is PSpace-complete. In both cases, we give a direct reduction from the satisfiability problem for (quantified) boolean formulae and we further show that the problems remain complete for their respective classes if we restrict the input alphabet of the automata to a binary one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10670 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Word Problem for Finitary Automaton Groups Kotowsky, Maximilian Wächter, Jan Philipp Formal Languages and Automata Theory Group Theory 20F10, 68Q17, 68Q45 F.4.m; F.2.2 A finitary automaton group is a group generated by an invertible, deterministic finite-state letter-to-letter transducer whose only cycles are self-loops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is coNP-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we also show that the respective compressed word problem, where the state sequence is given as a straight-line program, is PSpace-complete. In both cases, we give a direct reduction from the satisfiability problem for (quantified) boolean formulae and we further show that the problems remain complete for their respective classes if we restrict the input alphabet of the automata to a binary one. |
| title | The Word Problem for Finitary Automaton Groups |
| topic | Formal Languages and Automata Theory Group Theory 20F10, 68Q17, 68Q45 F.4.m; F.2.2 |
| url | https://arxiv.org/abs/2302.10670 |