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.

**[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)**

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