Decision problems for HNN groups and vector addition systems

Anshel, Michael

doi:10.1090/S0025-5718-1976-0396766-4

Decision problems for HNN groups and vector addition systems
HTML articles powered by AMS MathViewer

by Michael Anshel PDF

Math. Comp. 30 (1976), 154-156 Request permission

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

Michael Anshel, The endomorphisms of certain one-relator groups and the generalized Hopfian problem, Bull. Amer. Math. Soc. 77 (1971), 348–350. MR 272876, DOI 10.1090/S0002-9904-1971-12688-5
Michael Anshel, Non-Hopfian groups with fully invariant kernels. I, Trans. Amer. Math. Soc. 170 (1972), 231–237. MR 304491, DOI 10.1090/S0002-9947-1972-0304491-3
Michael Anshel, Non-Hopfian groups with fully invariant kernels. II, J. Algebra 24 (1973), 473–485. MR 313406, DOI 10.1016/0021-8693(73)90121-X
Michael Anshel, Conjugate powers in HNN groups, Proc. Amer. Math. Soc. 54 (1976), 19–23. MR 393249, DOI 10.1090/S0002-9939-1976-0393249-4
Michael Anshel and Peter Stebe, The solvability of the conjugacy problem for certain HNN groups, Bull. Amer. Math. Soc. 80 (1974), 266–270. MR 419615, DOI 10.1090/S0002-9904-1974-13455-5

Rabin’s Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems

Gilbert Baumslag, Residually finite one-relator groups, Bull. Amer. Math. Soc. 73 (1967), 618–620. MR 212078, DOI 10.1090/S0002-9904-1967-11799-3
Gilbert Baumslag and Donald Solitar, Some two-generator one-relator non-Hopfian groups, Bull. Amer. Math. Soc. 68 (1962), 199–201. MR 142635, DOI 10.1090/S0002-9904-1962-10745-9
John L. Britton, The word problem, Ann. of Math. (2) 77 (1963), 16–32. MR 168633, DOI 10.2307/1970200
Donald J. Collins, Recursively enumerable degrees and the conjugacy problem, Acta Math. 122 (1969), 115–160. MR 242671, DOI 10.1007/BF02392008

J. Reine Angew. Math.

Seymour Ginsburg, The mathematical theory of context-free languages, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR 0211815

Decision Problems for Petri Nets and Vector Addition Systems

Richard M. Karp and Raymond E. Miller, Parallel program schemata, J. Comput. System Sci. 3 (1969), 147–195. MR 246720, DOI 10.1016/S0022-0000(69)80011-5
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 234604, DOI 10.1145/321406.321418
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 260879, DOI 10.1090/S0002-9947-1970-0260879-9
A. Karrass and D. Solitar, Subgroups of $\textrm {HNN}$ groups and groups with one defining relation, Canadian J. Math. 23 (1971), 627–643. MR 301102, DOI 10.4153/CJM-1971-070-x
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
Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory: Presentations of groups in terms of generators and relations, Interscience Publishers [John Wiley & Sons], New York-London-Sydney, 1966. MR 0207802
Charles F. Miller III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 0310044
B. O. Nash, Reachability problems in vector addition systems, Amer. Math. Monthly 80 (1973), 292–295. MR 319420, DOI 10.2307/2318455
Alfred Pietrowski, The isomorphism problem for one-relator groups with non-trivial centre, Math. Z. 136 (1974), 95–106. MR 349851, DOI 10.1007/BF01214345