Algorithmically finite groups.

DOI10.1016/J.JPAA.2011.03.019MaRDI QIDQ640937zbMATHOpenAlexFDO

Authors Alexei Myasnikov, Denis Osin

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

zbMATH Keywords

algorithmsfinitely generated groupsconjugacy problemalgorithmically finite groupsrecursively presented groupsword problemequality problemDehn monsters

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.

Recommendations

• Algorithmic and asymptotic properties of groups.
• Algorithms for permutability in finite groups.
• scientific article; zbMATH DE number 1521041
• scientific article; zbMATH DE number 1860703
• An algorithm for constructing representations of finite groups.
• scientific article; zbMATH DE number 1419254
• scientific article; zbMATH DE number 5976624
• Algorithms for linear groups of finite rank.
• Finite subgroups of algebraic groups.
• scientific article; zbMATH DE number 1257081

Cites work

• scientific article; zbMATH DE number 3114412 (Why is no real title available?)
• scientific article; zbMATH DE number 3142911 (Why is no real title available?)
• scientific article; zbMATH DE number 3746135 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• scientific article; zbMATH DE number 67424 (Why is no real title available?)
• scientific article; zbMATH DE number 1955470 (Why is no real title available?)
• scientific article; zbMATH DE number 1535398 (Why is no real title available?)
• scientific article; zbMATH DE number 3220420 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3301426 (Why is no real title available?)
• scientific article; zbMATH DE number 3302312 (Why is no real title available?)
• scientific article; zbMATH DE number 3045417 (Why is no real title available?)
• A simple presentation of a group with unsolvable word problem
• Average-case complexity and decision problems in group theory.
• Cogrowth and amenability of discrete groups
• Elementary amenable groups
• Exponentially generic subsets of groups
• Generic complexity of undecidable problems
• Generic-case complexity, decision problems in group theory, and random walks.
• Golod-Shafarevich groups with property \((T)\) and Kac-Moody groups.
• Kazhdan quotients of Golod-Shafarevich groups (with an appendix on `Uniform non-amenability of Golod-Shafarevich groups' by Mikhail Ershov and Andrei Jaikin-Zapirain and an appendix on `Subgroup growth of Golod-Shafarevich groups' by Andrei Jaikin-Zapirain).
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Non-Backtracking Random Walks and Cogrowth of Graphs
• On the algorithmic insolvability of the word problem in group theory
• Recursive unsolvability of a problem of Thue
• Simple examples of groups with unsolvable word problem
• The Word Problem for Groups
• The halting problem is decidable on a set of asymptotic probability one
• The word problem

Cited in

(20)

• An algorithm computing homotopy groups.
• Residually finite algorithmically finite groups, their subgroups and direct products.
• Finitely presented expansions of groups, semigroups, and algebras
• Search problems in groups and branching processes.
• Asymptotic density and the theory of computability: a partial survey
• Algorithms for permutability in finite groups.
• Partial word and equality problems and Banach densities
• Computability theory. Abstracts from the workshop held January 7--13, 2018
• Algorithms determining finite simple images of finitely presented groups
• Algorithmic recognition of infinite cyclic extensions
• Algorithmic recognizability of the finiteness property of finite-definite systems
• Generalized algorithm for modeling periodic groups.
• Random equations in nilpotent groups.
• Golod-Shafarevich groups: a survey.
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• An algorithm for constructing representations of finite groups.
• Følner functions and the generic word problem for finitely generated amenable groups
• Classifying word problems of finitely generated algebras via computable reducibility
• Detecting properties from descriptions of groups
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics

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)