Decision problems for HNN groups and vector addition systems
Author:
Michael Anshel
Journal:
Math. Comp. 30 (1976), 154156
MSC:
Primary 20F10; Secondary 02G05, 68A10
MathSciNet review:
0396766
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Our purpose is to show the equivalence of the conjugacy problem for certain HNN extensions of the infinite cyclic groups and the reachability problem for the class of selfdual vector addition systems. In addition, we extend an endomorphism theorem of the author's to a homomorphism theorem and indicate a problem related to the isomorphism problem for a class of HNN groups.
 [1]
Michael
Anshel, The endomorphisms of certain
onerelator groups and the generalized Hopfian problem, Bull. Amer. Math. Soc. 77 (1971), 348–350. MR 0272876
(42 #7757), http://dx.doi.org/10.1090/S000299041971126885
 [2]
Michael
Anshel, NonHopfian groups with fully
invariant kernels. I, Trans. Amer. Math.
Soc. 170 (1972),
231–237. MR 0304491
(46 #3626), http://dx.doi.org/10.1090/S00029947197203044913
 [3]
Michael
Anshel, NonHopfian groups with fully invariant kernels. II,
J. Algebra 24 (1973), 473–485. MR 0313406
(47 #1960)
 [4]
Michael
Anshel, Conjugate powers in HNN
groups, Proc. Amer. Math. Soc. 54 (1976), 19–23. MR 0393249
(52 #14059), http://dx.doi.org/10.1090/S00029939197603932494
 [5]
Michael
Anshel and Peter
Stebe, The solvability of the conjugacy
problem for certain HNN groups, Bull. Amer.
Math. Soc. 80
(1974), 266–270. MR 0419615
(54 #7633), http://dx.doi.org/10.1090/S000299041974134555
 [6]
H. G. BAKER, JR, Rabin's Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems, CSG Memo 79, Project MAC, M.I.T., July 1973.
 [7]
Gilbert
Baumslag, Residually finite onerelator
groups, Bull. Amer. Math. Soc. 73 (1967), 618–620. MR 0212078
(35 #2953), http://dx.doi.org/10.1090/S000299041967117993
 [8]
Gilbert
Baumslag and Donald
Solitar, Some twogenerator onerelator
nonHopfian groups, Bull. Amer. Math. Soc.
68 (1962),
199–201. MR 0142635
(26 #204), http://dx.doi.org/10.1090/S000299041962107459
 [9]
John
L. Britton, The word problem, Ann. of Math. (2)
77 (1963), 16–32. MR 0168633
(29 #5891)
 [10]
Donald
J. Collins, Recursively enumerable degrees and the conjugacy
problem, Acta Math. 122 (1969), 115–160. MR 0242671
(39 #4001)
 [11]
G. FROBENIUS, "Theorie der linearen Formen mit gunzen Koeffizienten," J. Reine Angew. Math., v. 86, 1878, pp. 146208.
 [12]
Seymour
Ginsburg, The mathematical theory of contextfree languages,
McGrawHill Book Co., New YorkLondonSydney, 1966. MR 0211815
(35 #2692)
 [13]
M. HACK, Decision Problems for Petri Nets and Vector Addition Systems, CSC Memo 95, Project MAC, M.I.T., March 1974.
 [14]
Richard
M. Karp and Raymond
E. Miller, Parallel program schemata, J. Comput. System Sci.
3 (1969), 147–195. MR 0246720
(39 #8024)
 [15]
Richard
M. Karp, Raymond
E. Miller, and Shmuel
Winograd, The organization of computations for uniform recurrence
equations, J. Assoc. Comput. Mach. 14 (1967),
563–590. MR 0234604
(38 #2920)
 [16]
A.
Karrass and D.
Solitar, The subgroups of a free product of two
groups with an amalgamated subgroup, Trans.
Amer. Math. Soc. 150 (1970), 227–255. MR 0260879
(41 #5499), http://dx.doi.org/10.1090/S00029947197002608799
 [17]
A.
Karrass and D.
Solitar, Subgroups of 𝐻𝑁𝑁 groups and groups
with one defining relation, Canad. J. Math. 23
(1971), 627–643. MR 0301102
(46 #260)
 [18]
Jan
van Leeuwen, A partial solution to the reachabilityproblem for
vectoraddition systems, Sixth Annual ACM Symposium on Theory of
Computing (Seattle, Wash., 1974), Assoc. Comput. Mach., New York, 1974,
pp. 303–309. MR 0413611
(54 #1725)
 [19]
Wilhelm
Magnus, Abraham
Karrass, and Donald
Solitar, Combinatorial group theory: Presentations of groups in
terms of generators and relations, Interscience Publishers [John Wiley
& Sons, Inc.], New YorkLondonSydney, 1966. MR 0207802
(34 #7617)
 [20]
Charles
F. Miller III, On grouptheoretic decision problems and their
classification, Princeton University Press, Princeton, N.J.;
University of Tokyo Press, Tokyo, 1971. Annals of Mathematics Studies, No.
68. MR
0310044 (46 #9147)
 [21]
B.
O. Nash, Reachability problems in vector addition systems,
Amer. Math. Monthly 80 (1973), 292–295. MR 0319420
(47 #7964)
 [22]
Alfred
Pietrowski, The isomorphism problem for onerelator groups with
nontrivial centre, Math. Z. 136 (1974),
95–106. MR
0349851 (50 #2344)
 [1]
 M. ANSHEL, "The endomorphisms of certain onerelator groups and the generalized Hopfian problem," Bull. Amer. Math. Soc., v. 77, 1971, pp. 348350. MR 42 #7757. MR 0272876 (42:7757)
 [2]
 M. ANSHEL, "NonHopfian groups with fully invariant kernels. I," Trans. Amer. Math. Soc., v. 170, 1972, pp. 231237. MR 46 #3626. MR 0304491 (46:3626)
 [3]
 M. ANSHEL, "NonHopfian groups with fully invariant kernels. II," J. Algebra, v. 24, 1973, pp. 473485. MR 47 #1960. MR 0313406 (47:1960)
 [4]
 M. ANSHEL, "Conjugate powers in HNN groups," Proc. Amer. Math. Soc. (To appear.) MR 0393249 (52:14059)
 [5]
 M. ANSHEL & P. STEBE, "The solvability of the conjugacy problem for certain HNN groups," Bull. Amer. Math. Soc., v. 80, 1974, pp. 266270. MR 0419615 (54:7633)
 [6]
 H. G. BAKER, JR, Rabin's Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems, CSG Memo 79, Project MAC, M.I.T., July 1973.
 [7]
 G. BAUMSLAG, "Residually finite onerelator groups," Bull. Amer. Math. Soc., v. 73, 1967, pp. 618620. MR 35 #2953. MR 0212078 (35:2953)
 [8]
 G. BAUMSLAG & D. SOLITAR, "Some twogenerator onerelator nonHopfian groups," Bull. Amer. Math. Soc., v. 68, 1962, pp. 199201. MR 26 #204. MR 0142635 (26:204)
 [9]
 J. L. BRITTON, "The word problem," Ann. of Math. (2), v. 77, 1963, pp. 1632. MR 29 #5891. MR 0168633 (29:5891)
 [10]
 D. J. COLLINS, "Recursively enumerable degrees and the conjugacy problem," Acta Math., v. 122, 1969, pp. 115160. MR 39 #4001. MR 0242671 (39:4001)
 [11]
 G. FROBENIUS, "Theorie der linearen Formen mit gunzen Koeffizienten," J. Reine Angew. Math., v. 86, 1878, pp. 146208.
 [12]
 S. GINSBURG, The Mathematical Theory of ContextFree Languages, McGrawHill, New York, 1966. MR 35 #2692. MR 0211815 (35:2692)
 [13]
 M. HACK, Decision Problems for Petri Nets and Vector Addition Systems, CSC Memo 95, Project MAC, M.I.T., March 1974.
 [14]
 R. M. KARP & R. E. MILLER, "Parallel program schemata," J. Comput. System Sci., v. 3, 1969, pp. 147195. MR 39 #8024. MR 0246720 (39:8024)
 [15]
 R. M. KARP, R. E. MILLER & S. WINOGRAD, "The organization of computations for uniform recurrence equations," J. Assoc. Comput. Mach., v. 14, 1967, pp. 563590. MR 38 #2920. MR 0234604 (38:2920)
 [16]
 A. KARRASS & D. SOLITAR, "The subgroups of a free product of two groups with an amalgamated subgroup," Trans. Amer. Math. Soc., v. 150, 1970, pp. 227255. MR 41 #5499. MR 0260879 (41:5499)
 [17]
 A. KARRASS & D. SOLITAR, "Subgroups of HNN groups and groups with one defining relation," Canad. J. Math., v. 23, 1971, pp. 627643. MR 46 #260. MR 0301102 (46:260)
 [18]
 J. VAN LEEUWEN, "A partial solution to the reachability problem for vector addition systems," Proc. Sixth Annual ACM Symposium on the Theory of Computing, 1974, pp. 303309. MR 0413611 (54:1725)
 [19]
 W. MAGNUS, A. KARRASS & D. SOLITAR, Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, Pure and Appl. Math., vol. 13, Interscience, New York, 1966. MR 34 #7617. MR 0207802 (34:7617)
 [20]
 C. F. MILLER III, On GroupTheoretic Decision Problems and Their Classifications, Ann. of Math. Studies, no. 68, Princeton Univ. Press, Princeton, N. J.; Univ. of Tokyo Press, Tokyo, 1971. MR 46 #9147. MR 0310044 (46:9147)
 [21]
 B. O. NASH, "Reachability problems in vector addition systems," Amer. Math. Monthly, v. 80, 1973, pp. 292295. MR 47 #7964. MR 0319420 (47:7964)
 [22]
 A. PIETROWSKI, "The isomorphism problem for onerelator groups with nontrivial center," Math. Z., v. 136, 1974, pp. 95106. MR 0349851 (50:2344)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
20F10,
02G05,
68A10
Retrieve articles in all journals
with MSC:
20F10,
02G05,
68A10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197603967664
PII:
S 00255718(1976)03967664
Article copyright:
© Copyright 1976
American Mathematical Society
