Remarks and problems about algorithmic descriptions of groups
The paper is motivated by a theorem by \textit{D.~Groves} and \textit{H.~Wilton} [Groups Geom. Dyn. 3, No. 3, 389--399 (2009; Zbl 1216.20029)], which states that there exists an algorithm that, given as input a presentation for a group \(G\) and a solution to the word problem in \(G\), determines whether or not \(G\) is free. The author develops a systematic framework for studying global decision problems for finitely generated groups beyond the classical setting of finite presentations and proposes to study the lattice of numberings of isomorphism classes of marked groups as the natural environment for these questions. A marked group is a finitely generated group together with an ordered \(k\)-tuple of generators, considered up to marked isomorphism.\N\NThe work proves analogues of the classical Rice and Rice-Shapiro theorems in the setting of groups described by recursive and co-recursive presentations. These results show that semi-decidable properties of such groups correspond to Scott-open subsets of the lattice of marked groups and imply strong undecidability statements for global decision problems. The paper introduces the marked quotient problem and gives an algorithmic characterization of finitely presented groups as those with semi-decidable word problem and marked quotient problem (Theorem~G). It further develops the associated lattice-theoretic and topological structures and connects these with undecidability theorems.
- A NILPOTENT QUOTIENT ALGORITHM FOR CERTAIN INFINITELY PRESENTED GROUPS AND ITS APPLICATIONS
- A Note on Recursively Presented and Co-Recursively Presented Groups
- Admissible representations of effective cpo's
- Algorithmic operators in constructive metric spaces
- Algorithmically complex residually finite groups
- Asymptotic invariants, complexity of groups and related problems.
- Computability of finite quotients of finitely generated groups
- Computable abelian groups
- CONSTRUCTIVE ALGEBRAS I
- Coset enumeration for certain infinitely presented groups.
- DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
- Decision problems in classes of group presentations with uniformly solvable word problem
- Detecting properties from descriptions of groups
- Diophantine geometry over groups. I: Makanin-Razborov diagrams
- Embeddings in finitely presented groups which preserve the center.
- Endomorphic presentations of branch groups.
- Enumerating limit groups.
- Group Embeddings with Algorithmic Properties
- Hall's theorem for limit groups.
- scientific article; zbMATH DE number 5343235 (Why is no real title available?)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 67424 (Why is no real title available?)
- scientific article; zbMATH DE number 3560704 (Why is no real title available?)
- scientific article; zbMATH DE number 2086686 (Why is no real title available?)
- scientific article; zbMATH DE number 3316081 (Why is no real title available?)
- scientific article; zbMATH DE number 3110189 (Why is no real title available?)
- Limit groups as limits of free groups.
- Linear groups and computation
- Noncommutative real algebraic geometry of Kazhdan's property (T)
- On a Problem of J.H.C. Whitehead and a Problem of Alonzo Church.
- On effective topological spaces
- On Some Groups which cannot be Finitely Presented
- On the information carried by programs about the objects they compute
- On the integral homology of finitely presented groups
- On the isolated points in the space of groups.
- Papers on group theory and topology. Translated and introduced by John Stillwell
- Recursive metric spaces
- Representations of Lattices by Sets
- Some results related to the continuity problem
- Some Unsolvable Problems about Elements and Subgroups of Groups.
- The computational complexity of torsion-freeness of finitely presented groups
- The decision problem for some classes of sentences without quantifiers
- The isomorphism problem for finitely generated fully residually free groups.
- The isomorphism problem for residually torsion-free nilpotent groups.
- The isomorphism problem for toral relatively hyperbolic groups.
- The isomorphism problem for torsion-free abelian groups is analytic complete
- The metamathematics of algebraic systems. Collected papers: 1936-1967. Translated, edited, and provided with supplementary notes by Benjamin Franklin Wells III
- THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPS
- The triviality problem for profinite completions
- Word problems, embeddings, and free products of right-ordered groups with amalgamated subgroup
- Über unendliche diskontinuierliche Gruppen.
This page was built for publication: Remarks and problems about algorithmic descriptions of groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6923217)
