Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Containment Problem for Deterministic Multicounter Machine Models

  • Conference paper
  • First Online:
Automated Technology for Verification and Analysis (ATVA 2023)

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

  • 287 Accesses

Abstract

A new model of one-way multicounter machines is introduced. In this model, within each transition, testing the counter status of a counter is optional, rather than existing models where they are always either required (traditional multicounter machines) or no status can be checked (partially-blind multicounter machines). If, in every accepting computation, each counter has a bounded number of sections that decrease that counter where its status is tested, then the machine is called finite-testable. One-way nondeterministic finite-testable multicounter machines are shown to be equivalent to partially-blind multicounter machines, which, in turn, are known to be equivalent to Petri net languages and languages defined by vector addition systems with states. However, one-way deterministic finite-testable multicounter machines are strictly more general than deterministic partially-blind machines. Moreover, they also properly include deterministic reversal-bounded multicounter machines (unlike deterministic partially-blind multicounter machines). Interestingly, one-way deterministic finite-testable multicounter machines are shown to have a decidable containment problem (“given two machines \(M_1,M_2\), is \(L(M_1) \subseteq L(M_2)\)?”). This makes it the most general known model where this problem is decidable. We also study properties of their reachability sets.

The research of I. McQuillan was supported, in part, by Natural Sciences and Engineering Research Council of Canada.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8(3), 315–332 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  2. Baumann, P., et al.: Unboundedness problems for machines with reversal-bounded counters. In: 25th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) (2023)

    Google Scholar 

  3. Carpi, A., D’Alessandro, F., Ibarra, O.H., McQuillan, I.: Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity. Theoret. Comput. Sci. 862, 97–118 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  4. Crespi-Reghizzi, S., Pietro, P.S.: Deterministic counter machines and parallel matching computations. In: Proceedings of the 18th International Conference on Implementation and Application of Automata, CIAA 2013, vol. 7982, pp. 280–291 (2013)

    Google Scholar 

  5. Czerwiński, W., Hofman, P.: Language inclusion for boundedly-ambiguous vector addition systems is decidable. In: Klin, B., Lasota, S., Muscholl, A. (eds.) Proceedings of the 33rd International Conference on Concurrency Theory (CONCUR 2022), pp. 16:1–16:22 (2022)

    Google Scholar 

  6. Czerwinski, W., Hofman, P., Zetzsche, G.: Unboundedness problems for languages of vector addition systems. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, p. 119. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)

    Google Scholar 

  7. Eremondi, J., Ibarra, O.H., McQuillan, I.: Insertion operations on deterministic reversal-bounded counter machines. J. Comput. Syst. Sci. 104, 244–257 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gerth, R., Peled, D., Vardi, M.Y., Wolper, P.: Simple on-the-fly automatic verification of linear temporal logic. In: PSTV 1995. IAICT, pp. 3–18. Springer, Boston, MA (1996). https://doi.org/10.1007/978-0-387-34892-6_1

    Chapter  Google Scholar 

  9. Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill Inc, New York (1966)

    MATH  Google Scholar 

  10. Greibach, S.: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7, 311–324 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  11. Holzmann, G.J.: The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley, Boston (2003)

    Google Scholar 

  12. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, MA (1979)

    MATH  Google Scholar 

  13. Hopcroft, J.E., Pansiot, J.J.: On the reachability problem for 5-dimensional vector addition systems. Theoret. Comput. Sci. 8(2), 135–159 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  14. Ibarra, O., McQuillan, I.: The effect of end-markers on counter machines and commutativity. Theoret. Comput. Sci. 627, 71–81 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ibarra, O., Yen, H.: On the containment and equivalence problems for two-way transducers. Theoret. Comput. Sci. 429, 155–163 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Ibarra, O.H.: A note on semilinear sets and bounded-reversal multihead pushdown automata. Inf. Process. Lett. 3(1), 25–28 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  17. Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ibarra, O.H., Jiang, T., Tran, N., Wang, H.: New decidability results concerning two-way counter machines. SIAM J. Comput. 23(1), 123–137 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  19. Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. Int. J. Found. Comput. Sci. 23(6), 1291–1306 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kosaraju, S.R.: Decidability of reachability in vector addition systems. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC 1982, pp. 267–281 (1982)

    Google Scholar 

  21. Leroux, J.: Presburger vector addition systems. In: Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 23–32 (2013)

    Google Scholar 

  22. Mayr, E.W.: An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13(3), 441–460 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  23. Mottet, A., Quaas, K.: The containment problem for unambiguous register automata and unambiguous timed automata. Theory Comput. Syst. 65, 706–735 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  24. Parikh, R.: On context-free languages. J. ACM 13(4), 570–581 (1966)

    Article  MATH  Google Scholar 

  25. Pelz, E.: Closure properties of deterministic Petri nets. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds.) STACS 1987. LNCS, vol. 247, pp. 371–382. Springer, Heidelberg (1987). https://doi.org/10.1007/BFb0039620

    Chapter  Google Scholar 

  26. Rosenberg, A.L.: On multi-head finite automata. In: 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pp. 221–228 (1965)

    Google Scholar 

  27. Tang, N.V.: Pushdown Automata and Inclusion Problems. Ph.D. thesis, Japan Advanced Institute of Science and Technology, Japan (2007)

    Google Scholar 

  28. Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification. In: Chatterjee, K., Sgall, J. (eds.) Proceedings of the 1st IEEE Symposium Logic in Computer Science (LICS 1986), pp. 332–344. IEEE Computer Society (1986)

    Google Scholar 

  29. Vidal-Naquet, G.: Deterministic languages of Petri nets. In: Girault, C., Reisig, W. (eds.) Application and Theory of Petri Nets. Informatik-Fachberichte, vol. 52, pp. 198–202. Springer, Berlin (1981). https://doi.org/10.1007/978-3-642-68353-4_34

    Chapter  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of California, Santa Barbara, CA, 93106, USA

    Oscar H. Ibarra

  2. Department of Computer Science, University of Saskatchewan, Saskatoon, SK, S7N 5A9, Canada

    Ian McQuillan

Authors
  1. Oscar H. Ibarra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ian McQuillan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ian McQuillan .

Editor information

Editors and Affiliations

  1. Université Sorbonne Paris Nord, Villetaneuse, France

    Étienne André

  2. Singapore Management University, Singapore, Singapore

    Jun Sun

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ibarra, O.H., McQuillan, I. (2023). On the Containment Problem for Deterministic Multicounter Machine Models. In: André, É., Sun, J. (eds) Automated Technology for Verification and Analysis. ATVA 2023. Lecture Notes in Computer Science, vol 14215. Springer, Cham. https://doi.org/10.1007/978-3-031-45329-8_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45329-8_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45328-1

  • Online ISBN: 978-3-031-45329-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation