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]**Michael Anshel,*The endomorphisms of certain one-relator groups and the generalized Hopfian problem*, Bull. Amer. Math. Soc.**77**(1971), 348–350. MR**0272876**, https://doi.org/10.1090/S0002-9904-1971-12688-5**[2]**Michael Anshel,*Non-Hopfian groups with fully invariant kernels. I*, Trans. Amer. Math. Soc.**170**(1972), 231–237. MR**0304491**, https://doi.org/10.1090/S0002-9947-1972-0304491-3**[3]**Michael Anshel,*Non-Hopfian groups with fully invariant kernels. II*, J. Algebra**24**(1973), 473–485. MR**0313406**, https://doi.org/10.1016/0021-8693(73)90121-X**[4]**Michael Anshel,*Conjugate powers in HNN groups*, Proc. Amer. Math. Soc.**54**(1976), 19–23. MR**0393249**, https://doi.org/10.1090/S0002-9939-1976-0393249-4**[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**, https://doi.org/10.1090/S0002-9904-1974-13455-5**[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 one-relator groups*, Bull. Amer. Math. Soc.**73**(1967), 618–620. MR**0212078**, https://doi.org/10.1090/S0002-9904-1967-11799-3**[8]**Gilbert Baumslag and Donald Solitar,*Some two-generator one-relator non-Hopfian groups*, Bull. Amer. Math. Soc.**68**(1962), 199–201. MR**0142635**, https://doi.org/10.1090/S0002-9904-1962-10745-9**[9]**John L. Britton,*The word problem*, Ann. of Math. (2)**77**(1963), 16–32. MR**0168633**, https://doi.org/10.2307/1970200**[10]**Donald J. Collins,*Recursively enumerable degrees and the conjugacy problem*, Acta Math.**122**(1969), 115–160. MR**0242671**, https://doi.org/10.1007/BF02392008**[11]**G. FROBENIUS, "Theorie der linearen Formen mit gunzen Koeffizienten,"*J. Reine Angew. Math.*, v. 86, 1878, pp. 146-208.**[12]**Seymour Ginsburg,*The mathematical theory of context-free languages*, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR**0211815****[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**, https://doi.org/10.1016/S0022-0000(69)80011-5**[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**, https://doi.org/10.1145/321406.321418**[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**, https://doi.org/10.1090/S0002-9947-1970-0260879-9**[17]**A. Karrass and D. Solitar,*Subgroups of 𝐻𝑁𝑁 groups and groups with one defining relation*, Canad. J. Math.**23**(1971), 627–643. MR**0301102**, https://doi.org/10.4153/CJM-1971-070-x**[18]**Jan van Leeuwen,*A partial solution to the reachability-problem for vector-addition systems*, Sixth Annual ACM Symposium on Theory of Computing (Seattle, Wash., 1974), Assoc. Comput. Mach., New York, 1974, pp. 303–309. MR**0413611****[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 York-London-Sydney, 1966. MR**0207802****[20]**Charles F. Miller III,*On group-theoretic 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****[21]**B. O. Nash,*Reachability problems in vector addition systems*, Amer. Math. Monthly**80**(1973), 292–295. MR**0319420**, https://doi.org/10.2307/2318455**[22]**Alfred Pietrowski,*The isomorphism problem for one-relator groups with non-trivial centre*, Math. Z.**136**(1974), 95–106. MR**0349851**, https://doi.org/10.1007/BF01214345

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