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

- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0021-8693%2873%2990121-X - Michael Anshel,
*Conjugate powers in HNN groups*, Proc. Amer. Math. Soc.**54**(1976), 19β23. MR**393249**, DOI https://doi.org/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 https://doi.org/10.1090/S0002-9904-1974-13455-5
H. G. BAKER, JR, - Gilbert Baumslag,
*Residually finite one-relator groups*, Bull. Amer. Math. Soc.**73**(1967), 618β620. MR**212078**, DOI https://doi.org/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 https://doi.org/10.1090/S0002-9904-1962-10745-9 - John L. Britton,
*The word problem*, Ann. of Math. (2)**77**(1963), 16β32. MR**168633**, DOI https://doi.org/10.2307/1970200 - Donald J. Collins,
*Recursively enumerable degrees and the conjugacy problem*, Acta Math.**122**(1969), 115β160. MR**242671**, DOI https://doi.org/10.1007/BF02392008
G. FROBENIUS, "Theorie der linearen Formen mit gunzen Koeffizienten," - Seymour Ginsburg,
*The mathematical theory of context-free languages*, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR**0211815**
M. HACK, - Richard M. Karp and Raymond E. Miller,
*Parallel program schemata*, J. Comput. System Sci.**3**(1969), 147β195. MR**246720**, DOI https://doi.org/10.1016/S0022-0000%2869%2980011-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 https://doi.org/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 https://doi.org/10.1090/S0002-9947-1970-0260879-9 - A. Karrass and D. Solitar,
*Subgroups of ${\rm HNN}$ groups and groups with one defining relation*, Canadian J. Math.**23**(1971), 627β643. MR**301102**, DOI https://doi.org/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, Inc.], New York-London-Sydney, 1966. MR**0207802** - 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** - B. O. Nash,
*Reachability problems in vector addition systems*, Amer. Math. Monthly**80**(1973), 292β295. MR**319420**, DOI https://doi.org/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 https://doi.org/10.1007/BF01214345

*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.

*J. Reine Angew. Math.*, v. 86, 1878, pp. 146-208.

*Decision Problems for Petri Nets and Vector Addition Systems*, CSC Memo 95, Project MAC, M.I.T., March 1974.

Retrieve articles in *Mathematics of Computation*
with MSC:
20F10,
02G05,
68A10

Retrieve articles in all journals with MSC: 20F10, 02G05, 68A10

Additional Information

Article copyright:
© Copyright 1976
American Mathematical Society