Cellular Resource-Driven Automata

• Autorzy: Bashkin V.A. , Lomazova I.A.
• Języki publikacji: EN

Abstrakty

EN

Resource-driven automata (RDA) are finite automata, sitting in the nodes of a finite system net and asynchronously consuming/producing shared resources through input/output system ports (arcs of the system net). RDAs themselves may be resources for each other, thus allowing the highly flexible structure of the model. It was proved earlier, that RDA-nets are expressively equivalent to Petri nets [2]. In this paper the new formalism of cellular RDAs is introduced. Cellular RDAs are RDA-nets with an infinite regularly structured system net. We build a hierarchy of cellular RDA classes on the basis of restrictions on the underlying grid. The expressive power of several major classes of 1-dimensional grids is studied.

Słowa kluczowe

EN

multi-agent systems; mobile agents; Petri net; cellular nets; Resource-Driven Automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 3/4
• Strony: 243--257
• Opis fizyczny: Bibliogr. 17 poz., wykr.

Twórcy

autor

Bashkin V.A.

autor

Lomazova I.A.

• National Research University Higher School of Economics, Moscow, 101000, Russia,

Bibliografia

• [1] V.A. Bashkin. Nets of active resources for distributed systems modeling. Joint Bulletin of NCC&IIS, Comp. Science. vol. 28. Novosibirsk, 2008. P. 43-54.
• [2] V.A. Bashkin, I.A. Lomazova. Resource Driven Automata Nets. Fundamenta Informaticae. vol. 109(3). 2011. P. 223-236.
• [3] L. Chang, X. He, J. Lian, S. Shatz. Applying a Nested Petri Net Modeling Paradigm to Coordination of Sensor Networks with Mobile Agents. In Proc. of Workshop on Petri Nets and Distributed Systems 2008, Xian, China. 2008. P. 132-145.
• [4] S. Christensen. Decidability and Decomposition in Process Algebras. PhD thesis, Edinburgh University, 1993.
• [5] S. Christensen, Y. Hirshfeld, F. Moller. Bisimulation equivalence is decidable for Basic Parallel Processes. In E. Best (Ed.), Proc. of CONCUR'93. Lecture Notes in Computer Science, vol. 715. Springer, 1993.
• [6] M. Cook. Universality in Elementary Cellular Automata. Complex Systems. vol. 15. 2004. P. 1-40.
• [7] J. Esparza. Petri nets, commutative context-free grammars, and basic parallel processes, Fundamenta Informaticae. vol. 31. 1997. P. 13-26.
• [8] D. Goldin, D. Keil. Indirect Interaction in Environments for Multi-agent Systems. In D. Weyns, H. Parunak, F. Michel (Eds.), Environments for Multi-Agent Systems II. Lecture Notes in Computer Science, vol. 3830. Springer, 2005. P. 68-87.
• [9] P. Jančar. Decidability questions for bisimilarity of Petri nets and some related problems. In P. Enjalbert, E.W. Mayr, K.W. Wagner (Eds.), Proc. of STACS'94. Lecture Notes in Computer Science, vol. 775. Springer, 1994. P. 581-592.
• [10] M. Köhler-Bußmeier. Hornets: Nets within Nets combined with Net Algebra. In G. Franceschinis, K. Wolf (Eds.), Proc. of ICATPN'2009. Lecture Notes in Computer Science, vol.5606. Springer, 2009. P.243-262.
• [11] I.A. Lomazova. Nested Petri Nets - a Formalism for Specification and Verification of Multi-Agent Distributed Systems. Fundamenta Informaticae. vol.43. 2000. P.195-214.
• [12] I.A. Lomazova. Nested Petri nets for adaptive process modeling. In A. Avron, N. Dershowitz, A. Rabinovich (Eds.), Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday. Lecture Notes in Computer Science, vol. 4800. Springer, 2008. P. 413-426.
• [13] M. Minsky. Computation: Finite and Infinite Machines. Prentice Hall, 1967.
• [14] C.L. Nehaniv. Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network. Int.J. of Algebra and Computation. 2004. vol. 14(5-6). P. 719-739.
• [15] W. Pawlowski. Petri Hypernets with Constraints. In L. Czaja and M. Szczuka (Eds.), Proc. of the International Workshop on Concurrency, Specification, and Programming, CS&P'2009. P. 467-479.
• [16] R. Valk. Petri Nets as Token Objects: An Introduction to Elementary Object Nets. In J. Desel, M. Silva (Eds.), Proc. of ICATPN'98. Lecture Notes in Computer Science, vol.1420. Springer, 1998. P. 1-25.
• [17] S. Wolfram. Universality and Complexity in Cellular Automata. Physica D. vol. 10. 1984. P. 1-35.