Algorithmically finite groups.

DOI10.1016/J.JPAA.2011.03.019MaRDI QIDQ640937zbMATH OpenOpenAlexFDO

Publication date 21 October 2011

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.1653

algorithmically finite groups algorithms conjugacy problem Dehn monsters equality problem finitely generated groups recursively presented groups word problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: We call a group

G

{it algorithmically finite} if no algorithm can produce an infinite set of pairwise distinct elements of

G

. We construct examples of recursively presented infinite algorithmically finite groups and study their properties. For instance, we show that the Equality Problem is decidable in our groups only on strongly (exponentially) negligible sets of inputs.

Review text

The authors say that a finitely generated group is algorithmically finite if no algorithm can produce an infinite subset of the group. Using Golod-Shafarevich presentations as a tool, they build what they call Dehn monsters, that is infinite and recursively presented groups which are also algorithmically finite. They mention the challenging problem of imposing further the finite presentability of the group. The authors also study some properties of their Dehn monsters; for instance, they show that in such groups the Equality Problem is decidable only on sets of inputs which are strongly negligible in some appropriate sense.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Algorithmically finite groups.

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