Vernitski, Alexei (2009) One-side Nielsen transformations in free groups. International Journal of Algebra and Computation, 19 (07). pp. 855-871. DOI https://doi.org/10.1142/S0218196709005329
Vernitski, Alexei (2009) One-side Nielsen transformations in free groups. International Journal of Algebra and Computation, 19 (07). pp. 855-871. DOI https://doi.org/10.1142/S0218196709005329
Vernitski, Alexei (2009) One-side Nielsen transformations in free groups. International Journal of Algebra and Computation, 19 (07). pp. 855-871. DOI https://doi.org/10.1142/S0218196709005329
Abstract
We study a graph related to the Andrews-Curtis graph. The vertices are pairs of elements of a free group, and two vertices are adjacent if they can be obtained from one another by a left Nielsen transformation, that is, for each two words u, v the pair (u, v) is adjacent to (vu, v), (v‾¹u, v), (u, uv), and (u, u‾¹v). We study connected components of the graph and describe the shortest pairs in all components. Hence, we find a linear-time algorithm for checking whether two pairs belong to the same connected component of the graph.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Free group; Nielsen transformation; Andrews-Curtis graph; connected component; linear-time algorithm |
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 04 Jan 2012 11:17 |
| Last Modified: | 30 Oct 2024 20:09 |
| URI: | http://repository.essex.ac.uk/id/eprint/1804 |