Prohrak Kruengthomya ; Dmitry Berdinsky - Cayley Linear-Time Computable Groups

gcc:12503 - journal of Groups, complexity, cryptology, April 3, 2024, Volume 15, Issue 2 - https://doi.org/10.46298/jgcc.2024.15.2.12503
Cayley Linear-Time Computable GroupsArticle

Authors: Prohrak Kruengthomya ; Dmitry Berdinsky

    This paper looks at the class of groups admitting normal forms for which the right multiplication by a group element is computed in linear time on a multi-tape Turing machine. We show that the groups $\mathbb{Z}_2 \wr \mathbb{Z}^2$, $\mathbb{Z}_2 \wr \mathbb{F}_2$ and Thompson's group $F$ have normal forms for which the right multiplication by a group element is computed in linear time on a $2$-tape Turing machine. This refines the results previously established by Elder and the authors that these groups are Cayley polynomial-time computable.


    Volume: Volume 15, Issue 2
    Published on: April 3, 2024
    Accepted on: April 2, 2024
    Submitted on: November 3, 2023
    Keywords: Mathematics - Group Theory

    Consultation statistics

    This page has been seen 538 times.
    This article's PDF has been downloaded 205 times.