[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A multiparameter analysis of the boundedness problem for vector addition systems

  • Conference paper
  • First Online:
Fundamentals of Computation Theory (FCT 1985)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 199))

Included in the following conference series:

  • 124 Accesses

Abstract

Let VASS(k,l,n) denote the class of k-dimensional n-state Vector Addition Systems with States, where the largest integer mentioned, in an instance, can be represented in l bits. Using a modification of the technique used by Rackoff, we show that the Boundedness Problem (BP), for VASS(k,l,n), can be solved in O((l+log n)*2c*k*log k) nondeterministic space. By modifying Lipton's result, a lower bound is then shown of O((l+log n)*2c*k) nondeterministic space. Thus, the upper bound is optimal with respect to parameters l and n, and is nearly optimal with respect to the parameter k. This yields an improvement over the result of Rackoff, especially when compared with the lower bound of Lipton. This is because the lower bound, of O(2c*k) space, was essentially given for VASS(k,1,1). Now Rackoff's corresponding upper bound, just for the instances of VASS(k,1,1) constructed by Lipton, is no better than O(2c*k2*log k) space. (In general, it can get much worse.) Our result, however, yields an upper bound of O(2c*k*log k), over the entire class. We also investigate the complexity of this problem for small, but fixed, values of k. We show that the BP is PSPACE-complete for 4-dimensional VASS's, and NP-hard for 2-dimensional VASS's. The above results can then be extended for the case without states. In particular, we are able to show that the BP is NP-hard for VASS(3,l,1) and PSPACE-complete for VASS(4,l,1). Extensions to related problems (e.g. covering and reachability) are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Agerwala, T. and Flynn, M., Comments on Capabilities, Limitations, and ‘Correctness’ of Petri Nets, Proceedings of the First Annual Symposium on Computer Architecture, New York: ACM, 1973, pp. 81–86.

    Google Scholar 

  2. Borosh, I. and Treybis, L., Bounds on Positive Integral Solutions of Linear Diophantine Equations, Proc. AMS, Vol. 55, No. 2, pp. 299–304, March 1976.

    Google Scholar 

  3. Cook, S., Characterizations of Pushdown Machines in Terms of Time Bounded Computers, J. ACM, Vol. 18, No. 1, January 1971, pp. 4–18.

    Google Scholar 

  4. Cunha, P. and Maibaum, T., A Synchronous Calculus for Message Oriented Programming, Proceedings of the Second International Conference on Distributed Computing Systems, April 1981, pp. 443–445.

    Google Scholar 

  5. Garey, M. and Johnson, D., "Computers and Intractability: A Guide to the Theory of NP-Completeness", W. H. Freeman and Company, San Francisco, 1979.

    Google Scholar 

  6. Gouda, M., Gurari, E., Lai, T. and Rosier, L., Deadlock Detection in Systems of Communicating Finite State Machines, Tech. Rep. No. 84-11, University of Texas at Austin, Department of Computer Sciences, April 1984.

    Google Scholar 

  7. Gouda, M. and Rosier, L., Priority Networks of Communicating Finite State Machines, to appear in SIAM Journal on Computing, Vol. 14, No. 3, August 1985.

    Google Scholar 

  8. Gurari, E. and Lai, T., Deadlock Detection in Communicating Finite State Machines, ACM SIGACT NEWS, Vol. 15, No. 4, and Vol. 16, No. 1, Winter–Spring 1984, pp. 63–64.

    Google Scholar 

  9. Hack, M., Decidability Questions for Petri Nets, M.I.T., LCS, TR. 161, June 1976.

    Google Scholar 

  10. Hopcroft, J. and Pansiot, J., On the Reachability Problem for 5-Dimensional Vector Addition Systems, Theoret. Comp. Sci., Vol. 8, 1979, pp. 135–159.

    Google Scholar 

  11. Hopcroft, J. and Ullman, J., "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, Reading, Mass., 1979.

    Google Scholar 

  12. Jones, N., Landweber, L. and Lien, Y., Complexity of Some Problems in Petri Nets, Theoret. Comp. Sci., Vol. 8, 1979, pp. 277–299.

    Google Scholar 

  13. Kasai, T. and Iwata, S., Gradually Intractable Problems and Nondeterministic Log-Space Lower Bounds, to appear in Math. Systems Theory.

    Google Scholar 

  14. Karp, R. and Miller, R., Parallel Program Schemata, J. Computer and System Sciences, Vol. 3, No. 2, 1969, pp. 147–195.

    Google Scholar 

  15. Kosaraju, S., Limitations of Dijkstra's Semaphore Primitives and Petri Nets, Operating Systems Review, Vol. 7, No. 4, Oct. 1973, pp. 122–126.

    Google Scholar 

  16. Lawler, E., "Combinatorial Optimization: Networks and Matroids", Holt, Rinehart and Winston, New York, 1976.

    Google Scholar 

  17. Lipton, R., The Reachability Problem Requires Exponential Space, Yale University, Dept. of CS., Report No. 62, Jan., 1976.

    Google Scholar 

  18. Mayr, E. and Meyer, A., The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals, Advances in Mathematics, 46, 1982, pp. 305–329.

    Google Scholar 

  19. Minsky, M., "Computation: Finite and Infinite Machines", Prentice Hall, Englewood Cliffs, NJ, 1967.

    Google Scholar 

  20. Parnas, D., On a Solution to the Cigarette Smoker's Problem (Without Conditional Statements), Communications of the ACM, Vol. 18, No. 3, March 1975, pp. 181–183.

    Google Scholar 

  21. Patil, S., Limitations and Capabilities of Dijkstra's Semaphore Primitives for Coordination Among Processes, Group Memo 57, Project MAC, MIT, February 1971.

    Google Scholar 

  22. Peterson, J., "Petri Net Theory and the Modeling of Systems", Prentice Hall, Englewood Cliffs, NJ, 1981.

    Google Scholar 

  23. Rackoff, C., The Covering and Boundedness Problems for Vector Addition Systems, Theoret. Comp. Sci., Vol. 6, 1978, pp. 223–231.

    Google Scholar 

  24. Rosier, L. and Gouda, M., On Deciding Progress for a Class of Communication Protocols, Proceedings of the Eighteen Annual Conference on Information Science and Systems, Princeton Univ., 1984, pp. 663–667.

    Google Scholar 

  25. Rosier, L. and Yen, H., Boundedness, Empty Channel Detection and Synchronization for Communicating Finite State Machines, Proceedings of the Second Annual Symposium on Theoretical Aspects of Computer Science, Saarbrucken, West-Germany, 1985, pp. 287–298.

    Google Scholar 

  26. Savitch, W., Relationships between Nondeterministic and Deterministic Tape Complexities, J. of Computer and System Sciences, Vol. 4, No. 2, 1970, pp. 177–192.

    Google Scholar 

  27. Yu, Y. and Gouda, M., Unboundedness Detection for a Class of Communicating Finite State Machines, Information Processing Letters, Vol. 17, December 1983, pp. 235–240.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Sciences, University of Texas at Austin, 78712, Austin, Texas

    Louis E. Rosier & Hsu-Chun Yen

Authors
  1. Louis E. Rosier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hsu-Chun Yen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Lothar Budach

Rights and permissions

Reprints and permissions

Copyright information

© 1985 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Rosier, L.E., Yen, HC. (1985). A multiparameter analysis of the boundedness problem for vector addition systems. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol 199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028820

Download citation

  • DOI: https://doi.org/10.1007/BFb0028820

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-15689-5

  • Online ISBN: 978-3-540-39636-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation