Abstract
We study capacitated automata (CAs) [10], where transitions correspond to resources and have capacities, bounding the number of times they may be traversed. We follow the utilization semantics of CAs and view them as recognizers of multi-languages – sets of multisets of words, where a multiset S of words is in the multi-language of a CA A if all the words in S can be mutually accepted by A: the multiset of runs on all the words in S together respects the bounds induced by the capacities. Thus, capacitated automata model possible utilizations of systems with bounded resources. We study the basic properties of CAs: their expressive power in the nondeterministic and deterministic models, closure under classical operations, and the complexity of basic decision problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Not to be confused with finite capacity automata [12], which model the control of an automated manufacturing system, and are more related to Petri nets.
References
Boigelot, B., Godefroid, P.: Symbolic verification of communication protocols with infinite state spaces using QDDs. In: Alur, R., Henzinger, T.A. (eds.) CAV 1996. LNCS, vol. 1102, pp. 1–12. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61474-5_53
Bouajjani, A., Habermehl, P., Vojnar, T.: Verification of parametric concurrent systems with prioritised FIFO resource management. Formal Methods Syst. Des. 32(2), 129–172 (2008)
Cadilhac, M., Finkel, A., McKenzie, P.: On the expressiveness of Parikh automata and related models. In: 3rd Workshop on Non-Classical Models for Automata and Applications - NCMA, pp. 103–119 (2011)
Comon, H., Jurski, Y.: Multiple counters automata, safety analysis and presburger arithmetic. In: Hu, A.J., Vardi, M.Y. (eds.) CAV 1998. LNCS, vol. 1427, pp. 268–279. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0028751
Ford, L., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962)
Klaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 681–696. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45061-0_54
Krishnan, S., Puri, A., Brayton, R.: Deterministic \(\omega \)-automata vis-a-vis deterministic Büchi automata. In: Algorithms and Computations. Lecture Notes in Computer Science, vol. 834, pp. 378–386. Springer (1994)
Kupferman, O., Morgenstern, G., Murano, A.: Typeness for \(\omega \)-regular automata. Int. J. Found. Comput. Sci. 17(4), 869–884 (2006)
Kupferman, O., Sheinvald, S.: Capacitated automata and systems. Inf. Comput. 961, 269 (2019)
Kupferman, O., Tamir, T.: Properties and utilization of capacitated automata. In: Proceedings 34th Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 29, pp. 33–44. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2014)
Löding, C.: Optimal bounds for the transformation of \(\omega \)-automata. In: Proceedings 19th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1738, pp. 97–109 (1999)
Qiu, R., Joshi, S.: Deterministic finite capacity automata: a solution to reduce the complexity of modeling and control of automated manufacturing systems. In: Proceedings Symposium on Computer-Aided Control System Design, pp. 218–223 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Alon, R., Kupferman, O. (2020). Mutually Accepting Capacitated Automata. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)