Reducibilities among decision problems for HNN groups, vector addition systems and subsystems of Peano arithmetic

Authors:
Michael Anshel and Kenneth McAloon

Journal:
Proc. Amer. Math. Soc. **89** (1983), 425-429

MSC:
Primary 03D80; Secondary 03F30, 20F05, 20F10, 68Q99

MathSciNet review:
715859

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Our purpose is to exhibit reducibilities among decision problems for conjugate powers in HNN groups, reachability sets of vector addition systems and sentences in subsystems of Peano arithmetic, and show that although these problems are not primitive recursively decidable, they do admit decision procedures which are primitive recursive in the Ackermann function.

**[1]**Michael Anshel,*Vector groups and the equality problem for vector addition systems*, Math. Comp.**32**(1978), no. 142, 614–616. MR**482272**, 10.1090/S0025-5718-1978-0482272-7**[2]**Michel Hack,*The equality problem for vector addition systems is undecidable*, Theoret. Comput. Sci.**2**(1976), no. 1, 77–95. MR**0439610****[3]**Richard M. Karp and Raymond E. Miller,*Parallel program schemata*, J. Comput. System Sci.**3**(1969), 147–195. MR**0246720****[4]**L. A. S. Kirby and J. B. Paris,*Initial segments of models of Peano’s axioms*, Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619. MR**0491157****[5]**Roger C. Lyndon and Paul E. Schupp,*Combinatorial group theory*, Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. MR**0577064****[6]**E. Mayr,*The complexity of the finite containment problem for Petri nets*, Laboratory for Computer Science, Technical Report No. 181, M.I.T., Cambridge, Mass., 1977.**[7]**Kenneth McAloon,*Petri nets and large finite sets*, Theoret. Comput. Sci.**32**(1984), no. 1-2, 173–183. MR**761166**, 10.1016/0304-3975(84)90029-X**[8]**J. B. Paris,*A hierarchy of cuts in models of arithmetic*, Model theory of algebra and arithmetic (Proc. Conf., Karpacz, 1979), Lecture Notes in Math., vol. 834, Springer, Berlin-New York, 1980, pp. 312–337. MR**606791****[9]**James Lyle Peterson,*Petri net theory and the modeling of systems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981. MR**610984****[10]**Charles Rackoff,*The covering and boundedness problems for vector addition systems*, Theoret. Comput. Sci.**6**(1978), no. 2, 223–231. MR**486584**, 10.1016/0304-3975(78)90036-1**[11]**Gaisi Takeuti,*Proof theory*, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 81, North-Holland Publishing Co., Amsterdam, 1987. With an appendix containing contributions by Georg Kreisel, Wolfram Pohlers, Stephen G. Simpson and Solomon Feferman. MR**882549****[12]**Ann Yasuhara,*Recursive function theory and logic*, Academic Press, New York-London, 1971. Computer Science and Applied Mathematics. MR**0313027**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03D80,
03F30,
20F05,
20F10,
68Q99

Retrieve articles in all journals with MSC: 03D80, 03F30, 20F05, 20F10, 68Q99

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1983-0715859-8

Article copyright:
© Copyright 1983
American Mathematical Society