Recursively enumerable degress and the conjugacy problem

DOI10.1007/BF02392008zbMath0175.27501MaRDI QIDQ2533187

Donald J. Collins

Publication date: 1969

Published in: Acta Mathematica (Search for Journal in Brave)

zbMATH Keywords

constructive mathematicsrecursion theory

Related Items

The isomorphism problem for residually torsion-free nilpotent groups. ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ On some algorithmic problems for groups and monoids ⋮ On Cyclic Subgroups and the Conjugacy Problem ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ Class-preserving automorphisms of certain HNN extensions ⋮ Cyclic conjugacy separability and conjugacy separability of certain HNN extensions ⋮ Unnamed Item ⋮ Conjugacy separability and outer automorphism groups of certain HNN extensions. ⋮ GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS ⋮ Orbit decidability and the conjugacy problem for some extensions of groups ⋮ 1-genericity in the enumeration degrees ⋮ A FINITELY PRESENTED GROUP WITH ALMOST SOLVABLE CONJUGACY PROBLEM ⋮ On Conjugacy Separability of Fundamental Groups of Graphs of Groups ⋮ On the computability of conjugate powers in finitely generated Fuchsian groups ⋮ The Boone-Higman theorem and the conjugacy problem ⋮ Gröbner-Shirshov basis for the braid group in the Birman-Ko-Lee generators. ⋮ On the Conjugacy Problem for Cyclic Extensions of Free Groups ⋮ Unnamed Item ⋮ On recognising properties of groups which have solvable word problem ⋮ Embeddings into hopfian groups ⋮ Representation of Turing reducibility by word and conjugacy problems in finitely presented groups ⋮ Conjugacy separability of certain HNN extensions of groups. ⋮ Conjugacy in monoids with a special Church-Rosser presentation is decidable ⋮ Class-preserving automorphisms of certain HNN extensions. ⋮ Model-theoretic and algorithmic questions in group theory ⋮ The Isomorphism Problem for Two-Generator One-Relator Groups with Torsion is Solvable ⋮ The word problem for division rings ⋮ Complexity results on the conjugacy problem for monoids

Cites Work

• Recursive unsolvability of group theoretic problems
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• The word problem
• The word problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item