Publication: Cayley polynomial–time computable groups
Issued Date
2021-01-01
Resource Type
ISSN
10902651
08905401
08905401
Other identifier(s)
2-s2.0-85107451567
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Information and Computation. (2021)
Suggested Citation
Dmitry Berdinsky, Murray Elder, Prohrak Kruengthomya Cayley polynomial–time computable groups. Information and Computation. (2021). doi:10.1016/j.ic.2021.104768 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/76744
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Cayley polynomial–time computable groups
Author(s)
Abstract
We propose a new generalization of Cayley automatic groups, varying the time complexity of computing multiplication, and language complexity of the normal form representatives. We first consider groups which have normal form language in the class C and multiplication by generators computable in linear time on a certain restricted Turing machine model (position–faithful one–tape). We show that many of the algorithmic properties of automatic groups are preserved, prove various closure properties, and show that the class is quite large. We then generalize to groups which have normal form language in the class C and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when C=REG (the class of regular languages). We prove that REG–Cayley polynomial–time computable groups include all finitely generated nilpotent groups, the wreath product Z2≀Z2, and Thompson's group F.