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), 425429
MSC:
Primary 03D80; Secondary 03F30, 20F05, 20F10, 68Q99
MathSciNet review:
715859
Fulltext 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
(81e:20042), http://dx.doi.org/10.1090/S00255718197804822727
 [2]
Michel
Hack, The equality problem for vector addition systems is
undecidable, Theoret. Comput. Sci. 2 (1976),
no. 1, 77–95. MR 0439610
(55 #12496)
 [3]
Richard
M. Karp and Raymond
E. Miller, Parallel program schemata, J. Comput. System Sci.
3 (1969), 147–195. MR 0246720
(39 #8024)
 [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 (58 #10423)
 [5]
Roger
C. Lyndon and Paul
E. Schupp, Combinatorial group theory, SpringerVerlag,
BerlinNew York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete,
Band 89. 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]
Kenneth
McAloon, Petri nets and large finite sets, Theoret. Comput.
Sci. 32 (1984), no. 12, 173–183. MR 761166
(86g:68130), http://dx.doi.org/10.1016/03043975(84)90029X
 [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, BerlinNew York, 1980,
pp. 312–337. MR 606791
(84e:03085)
 [9]
James
Lyle Peterson, Petri net theory and the modeling of systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1981. MR 610984
(82j:68017)
 [10]
Charles
Rackoff, The covering and boundedness problems for vector addition
systems, Theoret. Comput. Sci. 6 (1978), no. 2,
223–231. MR
486584 (81e:68024), http://dx.doi.org/10.1016/03043975(78)900361
 [11]
Gaisi
Takeuti, Proof theory, 2nd ed., Studies in Logic and the
Foundations of Mathematics, vol. 81, NorthHolland Publishing Co.,
Amsterdam, 1987. With an appendix containing contributions by Georg
Kreisel, Wolfram Pohlers, Stephen G. Simpson and Solomon Feferman. MR 882549
(89a:03115)
 [12]
Ann
Yasuhara, Recursive function theory and logic, Academic Press,
New YorkLondon, 1971. Computer Science and Applied Mathematics. MR 0313027
(47 #1582)
 [1]
 M. Anshel, Vector groups and the equality problem for vector addition systems, Math. Comp. 32 (1978), 614616. MR 482272 (81e:20042)
 [2]
 M. Hack, The equality problem for vector addition systems is undecidable, Theoret. Comput. Sci. 2 (1976), 7796. MR 0439610 (55:12496)
 [3]
 R. M. Karp and R. E. Miller, Parellel program schemata, J. Comput. System Sci. 3.(1969), 147195. 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, SpringerVerlag, Berlin, 1977. MR 0491157 (58:10423)
 [5]
 R. C. Lyndon and P. E. Schupp, Combinatorial group theory, SpringerVerlag, 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, SpringerVerlag, Berlin, 1980. MR 606791 (84e:03085)
 [9]
 J. L. Peterson, Petri nets and the modelling of systems, PrenticeHall, 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), 223231. MR 486584 (81e:68024)
 [11]
 G. Takeuti, Proof theory, NorthHolland, 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
DOI:
http://dx.doi.org/10.1090/S00029939198307158598
PII:
S 00029939(1983)07158598
Article copyright:
© Copyright 1983
American Mathematical Society
