A partial solution to the reachability-problem for vector-addition systems

ABSTRACT

With geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory but unsolved ever since it was proposed by Karp and Miller. We show that the reachability-problem is decidable in dim. ≤ 3 and give a partial solution for the general problem covering a wide instance of it. In both cases a semi-linear characterization is obtained for the complete set of solutions. Contrary to common belief the complete solution in dim. 3 does not immediately generalize, and our analysis gives evidence why. A few generalizations and application to long-standing classificational problems in language theory are discussed.

REFERENCES

• 1: Abraham, S., On matrix grammars, Techn. Rep. 3, Dept. of Computer Science, Technion, Haifa, Israel, 1970.
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Aitchison, P. W., and G. T. Herman, *A decision-procedure using the geometry of convex sets,# (to appear), 1974.
• 4: Baker, B. S., On finding non-negative integer solutions to sets of linear equations, Harvard Univ., Cambridge, Mass., 1974.
• 5: Bancilhon, F., A geometrical model for a stochastic automaton, DAIMI-PB 15, 73-76, Dept. of Computer Science, Aarhus, Denmark, 1973.
• 6: Conway, J. H., #Unpredictable iterations, Proc. 1972 Number Theory Conf., Univ. of Colorado, Boulder, 49-52.
• 7: Frobenius, G., Theorie der linearen Formen mit ganzen Koeffizienten, J. f. Math., Bd. 86 (1878) 146-208.
• 8: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 9: Hegner, I., Ueber die Auflösung eines Systems von Mehreren unbestimmten Gleichungen des ersten Grades in ganzen Zahlen, Denkschr. Akad. Wiss. Wien, Math.-naturw. Kl., Bd 14 II (1858) 1-122.
• 10: Herman, G. T., and J. A. Jackowski, A decision procedure using discrete geometry, Discr. Math. 5 (1973) 131-144.
• 11: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 12: Karp, R. M., and R. E. Miller, Parallel program-schemata, JCSS 3 (1969) 147-195.
• 13: Robert M. Keller, Parallel Program Schemata and Maximal Parallelism I. Fundamental Results, Journal of the ACM (JACM), v.20 n.3, p.514-537, July 1973 [doi>10.1145/321765.321782]
• 14: Maurer, M. A., private communication, Ohio, 1973.
• 15: Bobby Otis Nash, Context-free parallel leveled languages, 1970
• 16: Nash, B. O., Reachability-problems in vector-addition systems, Amer. Math. Monthly 80 (1973) 292-295 (Research Problem Section).
• 17: Rohit J. Parikh, On Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.570-581, Oct. 1966 [doi>10.1145/321356.321364]
• 18: Penttonen, M., private communication, Aarhus, 1974.
• 19: Rabin, M. O., private correspondence.
• 20: Daniel J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages, Journal of the ACM (JACM), v.16 n.1, p.107-131, Jan. 1969 [doi>10.1145/321495.321504]
• 21: Salomaa, A., On grammars with restricted use of productions, Ann. Acad. Sci. Fenn., Ser AI, Helsinki, 1969.
• 22: Salomaa, A., Matrix grammars with the leftmost restriction, Inf. and Control 20 (1972) 143-149.
• 23: Arto Salomaa, Formal languages, Academic Press Professional, Inc., San Diego, CA, 1987
• 24: Skolem, Th., Diophantische Gleichungen, Chelsea Publ. Co., New York, 1950.
• 25: van Leeuwen, J., Rule-labeled programs, Ph.D. thesis, Math. Dept., University of Utrecht, Netherlands, 1972.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Theory