Cayley Polynomial-Time Computable Groups

DOI10.1016/J.IC.2021.104768MaRDI QIDQ6346593arXivFDO

Authors D. A. Berdinskij, Murray Elder, Prohrak Kruengthomya

Publication date 6 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.IC.2021.104768

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

arXiv classification

math.GRcs.FL

Abstract: We propose a new generalisation 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 $mathcalC$ 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 (quadratic time word problem), prove various closure properties, and show that the class is quite large; for example it includes all virtually polycyclic groups. We then generalise to groups which have normal form language in the class $mathcalC$ and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when $mathcalC=mathrmREG$ (the class of regular languages). We prove that $mathrmREG$-Cayley polynomial-time computable groups includes all finitely generated nilpotent groups, the wreath product $mathbb{Z}_{2}wrmathbb{Z}^2$, and Thompson's group $F$.

This page was built for publication: Cayley Polynomial-Time Computable Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346593)