CAYLEY LINEAR–TIME COMPUTABLE GROUPS
Issued Date
2024-01-01
Resource Type
eISSN
18696104
Scopus ID
2-s2.0-85190769903
Journal Title
Groups, Complexity, Cryptology
Volume
15
Issue
2
Start Page
1:1
End Page
1:22
Rights Holder(s)
SCOPUS
Bibliographic Citation
Groups, Complexity, Cryptology Vol.15 No.2 (2024) , 1:1-1:22
Suggested Citation
Kruengthomya P., Berdinsky D. CAYLEY LINEAR–TIME COMPUTABLE GROUPS. Groups, Complexity, Cryptology Vol.15 No.2 (2024) , 1:1-1:22. 1:22. doi:10.46298/jgcc.2024.15.2.12503 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/98127
Title
CAYLEY LINEAR–TIME COMPUTABLE GROUPS
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
Abstract
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 Z2 ≀ Z2, Z2 ≀ F2 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.