Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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.

References [Enhancements On Off] (What's this?)

  • [1] M. Anshel, Vector groups and the equality problem for vector addition systems, Math. Comp. 32 (1978), 614-616. MR 482272 (81e:20042)
  • [2] M. Hack, The equality problem for vector addition systems is undecidable, Theoret. Comput. Sci. 2 (1976), 77-96. MR 0439610 (55:12496)
  • [3] R. M. Karp and R. E. Miller, Parellel program schemata, J. Comput. System Sci. 3.(1969), 147-195. MR 0246720 (39:8024)
  • [4] L. Kirby and J. Paris, Initial segments of models of arithmetic, Set Theory and Hierarchy Theory V, Lecture Notes in Math., Vol. 619, Springer-Verlag, Berlin, 1977. MR 0491157 (58:10423)
  • [5] R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Springer-Verlag, Berlin, 1977. MR 0577064 (58:28182)
  • [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] K. McAloon, Petri nets and large finite sets, Theoret. Comput. Sci. (to appear). MR 761166 (86g:68130)
  • [8] J. Paris, Hierarchy of cuts in models of arithmetic, Model Theory of Algebra and Arithmetic, Lecture Notes in Math., Vol. 834, Springer-Verlag, Berlin, 1980. MR 606791 (84e:03085)
  • [9] J. L. Peterson, Petri nets and the modelling of systems, Prentice-Hall, Englewood Cliffs, N. J., 1981. MR 610984 (82j:68017)
  • [10] C. Rackoff, The covering and boundedness problems for vector addition systems, Theoret. Comput. Sci. 6 (1978), 223-231. MR 486584 (81e:68024)
  • [11] G. Takeuti, Proof theory, North-Holland, Amsterdam, 1975. MR 882549 (89a:03115)
  • [12] A. Yashuhara, Recursive function theory and logic, Academic Press, New York, 1971. MR 0313027 (47:1582)

Similar Articles

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

Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society