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

Anshel, Michael; McAloon, Kenneth

doi:10.1090/S0002-9939-1983-0715859-8

Reducibilities among decision problems for HNN groups, vector addition systems and subsystems of Peano arithmetic
HTML articles powered by AMS MathViewer

by Michael Anshel and Kenneth McAloon PDF

Proc. Amer. Math. Soc. 89 (1983), 425-429 Request permission

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

Michael Anshel, Vector groups and the equality problem for vector addition systems, Math. Comp. 32 (1978), no. 142, 614–616. MR 482272, DOI 10.1090/S0025-5718-1978-0482272-7
Michel Hack, The equality problem for vector addition systems is undecidable, Theoret. Comput. Sci. 2 (1976), no. 1, 77–95. MR 439610, DOI 10.1016/0304-3975(76)90008-6
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
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) Lecture Notes in Math., Vol. 619, Springer, Berlin, 1977, pp. 211–226. MR 0491157
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064

The complexity of the finite containment problem for Petri nets

Kenneth McAloon, Petri nets and large finite sets, Theoret. Comput. Sci. 32 (1984), no. 1-2, 173–183. MR 761166, DOI 10.1016/0304-3975(84)90029-X
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
James Lyle Peterson, Petri net theory and the modeling of systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981. MR 610984
Charles Rackoff, The covering and boundedness problems for vector addition systems, Theoret. Comput. Sci. 6 (1978), no. 2, 223–231. MR 486584, DOI 10.1016/0304-3975(78)90036-1
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
Ann Yasuhara, Recursive function theory and logic, Computer Science and Applied Mathematics, Academic Press, New York-London, 1971. MR 0313027