Publication: Cayley polynomial–time computable groups
20
item.page.dc.date.issued
2021-01-01
item.page.dc.type
item.page.dc.identifier.issn
10902651
08905401
08905401
item.page.dc.identifier.doi
item.page.dc.identifier.other
2-s2.0-85107451567
item.page.dc.rights
Mahidol University
item.page.dc.rights.holder
SCOPUS
item.page.dc.identifier.citation
Information and Computation. (2021)
punsarn.item.page.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/123456789/76744
Research Projects
Organizational Units
Authors
Journal Issue
relationships.isThesisOf
item.page.dc.title
Cayley polynomial–time computable groups
item.page.dc.contributor.author
item.page.dc.contributor.other
item.page.dc.description.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.
