Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Decision problems for HNN groups and vector addition systems


Author: Michael Anshel
Journal: Math. Comp. 30 (1976), 154-156
MSC: Primary 20F10; Secondary 02G05, 68A10
DOI: https://doi.org/10.1090/S0025-5718-1976-0396766-4
MathSciNet review: 0396766
Full-text PDF

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 self-dual 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.


References [Enhancements On Off] (What's this?)

  • [1] M. ANSHEL, "The endomorphisms of certain one-relator groups and the generalized Hopfian problem," Bull. Amer. Math. Soc., v. 77, 1971, pp. 348-350. MR 42 #7757. MR 0272876 (42:7757)
  • [2] M. ANSHEL, "Non-Hopfian groups with fully invariant kernels. I," Trans. Amer. Math. Soc., v. 170, 1972, pp. 231-237. MR 46 #3626. MR 0304491 (46:3626)
  • [3] M. ANSHEL, "Non-Hopfian groups with fully invariant kernels. II," J. Algebra, v. 24, 1973, pp. 473-485. 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. 266-270. 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 one-relator groups," Bull. Amer. Math. Soc., v. 73, 1967, pp. 618-620. MR 35 #2953. MR 0212078 (35:2953)
  • [8] G. BAUMSLAG & D. SOLITAR, "Some two-generator one-relator non-Hopfian groups," Bull. Amer. Math. Soc., v. 68, 1962, pp. 199-201. MR 26 #204. MR 0142635 (26:204)
  • [9] J. L. BRITTON, "The word problem," Ann. of Math. (2), v. 77, 1963, pp. 16-32. MR 29 #5891. MR 0168633 (29:5891)
  • [10] D. J. COLLINS, "Recursively enumerable degrees and the conjugacy problem," Acta Math., v. 122, 1969, pp. 115-160. 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. 146-208.
  • [12] S. GINSBURG, The Mathematical Theory of Context-Free Languages, McGraw-Hill, 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. 147-195. 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. 563-590. 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. 227-255. 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. 627-643. 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. 303-309. 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 Group-Theoretic 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. 292-295. MR 47 #7964. MR 0319420 (47:7964)
  • [22] A. PIETROWSKI, "The isomorphism problem for one-relator groups with non-trivial center," Math. Z., v. 136, 1974, pp. 95-106. 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: https://doi.org/10.1090/S0025-5718-1976-0396766-4
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society