Algorithmically finite groups.

DOI10.1016/J.JPAA.2011.03.019zbMATH Open1233.20031arXiv1012.1653OpenAlexW1979073518MaRDI QIDQ640937FDOQ640937

Authors: Alexei Myasnikov, Denis Osin 

Publication date: 21 October 2011

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generic complexity of undecidable problems
• Title not available (Why is that?)
• Recursive unsolvability of a problem of Thue
• Elementary amenable groups
• Cogrowth and amenability of discrete groups
• Non-Backtracking Random Walks and Cogrowth of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generic-case complexity, decision problems in group theory, and random walks.
• On the algorithmic insolvability of the word problem in group theory
• The word problem
• Golod-Shafarevich groups with property \((T)\) and Kac-Moody groups.
• Title not available (Why is that?)
• A simple presentation of a group with unsolvable word problem
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Average-case complexity and decision problems in group theory.
• Exponentially generic subsets of 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).
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The halting problem is decidable on a set of asymptotic probability one
• Simple examples of groups with unsolvable word problem
• The Word Problem for Groups
• Title not available (Why is that?)

Cited In (17)

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

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)