maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-4-391-409mais-530Research ArticleОригинальные статьиArticlesО пространственной ограниченности клеточных Р-сетейOn the Spatial Boundedness of Cellular RDA-netshttps://orcid.org/0000-0002-2534-1026БашкинВладимир АнатольевичBashkinVladimir A.

д-р физ.-мат. наук, доцент

PhD

v_bashkin@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201731082017244391409Copyright © Башкин В.А., 20172017Башкин В.А.Bashkin V.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/530

Клеточные Р-сети — обобщение концепции двухуровневых ресурсных сетей (сетей Петри) на случай бесконечной регулярной системной решетки. Этот формализм представляет собой гибрид сетей Петри и асинхронных клеточных автоматов и предназначен для моделирования мультиагентных систем с динамической пространственной структурой. Пространственная ограниченность — свойство, гарантирующее сохранение конечности “геометрических размеров” (например, площади) активной части системы на протяжении всей её жизни. Определяются три варианта пространственной ограниченности для клеточных Р-сетей: локализованность, ограниченность диаметра и ограниченность площади. Исследуются свойства соответствующих алгоритмических проблем, доказывается их неразрешимость в общем случае. Предлагается нетривиальный критерий локализованности одномерной клеточной сети, основанный на новой концепции графа распространения Р-автоматов. Описывается алгоритм построения графа распространения, использующий метод насыщения генерирующих путей. Предлагается способ оценки сверху диаметра одномерной клеточной сети с ограниченным графом распространения.

Cellular resource driven automata nets (CRDA-nets) is a generalization of the concept of two-level resource nets (Petri nets) with an infinite regular system grid. This formalism is a hybrid of Petri nets and asynchronous Cellular Automata and is designed for modeling multi-agent systems with dynamic spatial structure. Spatial boundedness is a property that guarantees the preservation of the finiteness of “geometric dimensions” of the active part of the system (for example, the living space) during its lifetime. Three variants of spatial boundedness for cellular RDA-nets are defined: localization, bounded diameter and bounded area. The properties of the corresponding algorithmic problems are investigated, their undecidability in the general case is proved. A non-trivial criterion for the localization of an one-dimensional CRDA-net is proposed, based on the new concept of the RDA propagation graph. An algorithm is described for constructing a propagation graph, using the method of saturation of generating paths. A method for estimating the diameter of an 1-dim CRDA with a bounded propagation graph is presented.

мультиагентные системыверификациясети Петриклеточные автоматыР-сетипространственная ограниченностьmultiagent systemsverificationPetri netscellular automataresource driven automata netsspatial boundednessReferencesБашкин В. А., “Сети активных ресурсов”, Моделирование и анализ информационных систем, 14:4 (2007), 13-19Bashkin V.A., “Nets of active resources”, Model. Anal. Inform. Sist., 14:4 (2007), 13-19, (in Russian).Башкин В. А., “Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов”, Программирование, 36:4 (2010), 3-15Bashkin V. A., “Formalization of semantics of systems with unreliable agents by means of nets of active resources”, Progr. and Comp. Soft., 36:4 (2010), 187-196Зайцев Д. А., “Верификация вычислительных решеток с особыми краевыми условиями бесконечными сетями Петри”, Моделирование и анализ информационных систем, 19:6 (2012), 21-33Zaitsev D. A., “Verification of computing grids with special edge conditions by infinite Petri nets”, Automatic Control and Computer Sciences, 47:7 (2013), 403-412Котов В. Е., Сети Петри, Наука, М., 1984Kotov V. E., Seti Petri, Nauka, Moskva, 2008, (in Russian)Кузьмин Е. В., Чалый Д.Ю., “О разрешимости проблем ограниченности для счетчиковых машин Минского”, Моделирование и анализ информационных систем, 15:1 (2008), 16-26Kuzmin E. V., Chalyy D. Ju., “On the decidability of boundedness problems for counter Minsky machines”, Model. Anal. Inform. Sist., 15:1 (2008), 16-26. (in Russian).Alur R., Dill D., “Automata for modeling real-time systems” (Automata, Languages and Programming), Lecture Notes In Computer Science, 443 (1990), 322-335.Alur R., Dill D., “Automata for modeling real-time systems” (Automata, Languages and Programming), Lecture Notes In Computer Science, 443 (1990), 322-335.Bashkin V. A., “Nets of active resources for distributed systems modeling”, Joint Bulletin of NCC&IIS, Comp. Science, 28 (2008), 43-54.Bashkin V. A., “Nets of active resources for distributed systems modeling”, Joint Bulletin of NCC&IIS, Comp. Science, 28 (2008), 43-54.Bashkin V. A., Lomazova I. A., “Resource Driven Automata Nets”, Fundamenta Informaticae, 109:3 (2011), 223-236.Bashkin V. A., Lomazova I. A., “Resource Driven Automata Nets”, Fundamenta Informaticae, 109:3 (2011), 223-236.Bashkin V. A., Lomazova I. A., “Cellular Resource Driven Automata Nets”, Fundamenta Informaticae, 120:3-4 (2012), 245-259.Bashkin V. A., Lomazova I. A., “Cellular Resource Driven Automata Nets”, Fundamenta Informaticae, 120:3-4 (2012), 245-259.Bashkin V. A., Lomazova I. A., Novikova Yu. A., “Timed Resource Driven Automata Nets for Distributed Real-Time Systems Modelling” (Parallel Computing Technologies), Lecture Notes In Computer Science, 7979 (2013), 13-25.Bashkin V. A., Lomazova I. A., Novikova Yu. A., “Timed Resource Driven Automata Nets for Distributed Real-Time Systems Modelling” (Parallel Computing Technologies), Lecture Notes In Computer Science, 7979 (2013), 13-25.Bednarczyk M. A., Bernardinello L., Pawlowski W., Pomello L., “Modelling mobility with Petri Hypernets” (Recent Trends in Algebraic Development Techniques), Lecture Notes In Computer Science, 3423 (2005), 28-44.Bednarczyk M. A., Bernardinello L., Pawlowski W., Pomello L., “Modelling mobility with Petri Hypernets” (Recent Trends in Algebraic Development Techniques), Lecture Notes In Computer Science, 3423 (2005), 28-44.Cook M., “Universality in Elementary Cellular Automata.”, Complex Systems, 15:1 (2004), 1-40.Cook M., “Universality in Elementary Cellular Automata.”, Complex Systems, 15:1 (2004), 1-40.Finkel A., Schnoebelen Ph., “Well-Structured Transition Systems Everywhere!”, Theoretical Computer Science, 256:1-2 (2001), 63-92.Finkel A., Schnoebelen Ph., “Well-Structured Transition Systems Everywhere!”, Theoretical Computer Science, 256:1-2 (2001), 63-92.Jensen K., Colored Petri Nets: Basic Concepts, Analysis Methods and Practical Use, Springer, 1994.Jensen K., Colored Petri Nets: Basic Concepts, Analysis Methods and Practical Use, Springer, 1994.K¨ohler-Bußmeier M., “Hornets: Nets within Nets combined with Net Algebra” (ICATPN’2009), Lecture Notes In Computer Science, 5606 (2009), 243-262.K¨ohler-Bußmeier M., “Hornets: Nets within Nets combined with Net Algebra” (ICATPN’2009), Lecture Notes In Computer Science, 5606 (2009), 243-262.Lomazova I. A., “Nested Petri Nets - a Formalism for Specification and Verification of Multi-Agent Distributed Systems”, Fundamenta Informaticae, 43:1-4 (2000), 195-214.Lomazova I. A., “Nested Petri Nets - a Formalism for Specification and Verification of Multi-Agent Distributed Systems”, Fundamenta Informaticae, 43:1-4 (2000), 195-214.Nehaniv C. L., “Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network”, Int. J. of Algebra and Computation, 14:5-6 (2004), 719-739.Nehaniv C. L., “Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network”, Int. J. of Algebra and Computation, 14:5-6 (2004), 719-739.Petri C. A., Kommunikation mit Automaten. PhD thesis, Bonn Institute f¨ur Instrumentelle Mathematik, 1962.Petri C. A., Kommunikation mit Automaten. PhD thesis, Bonn Institute f¨ur Instrumentelle Mathematik, 1962.Valk R., “Petri Nets as Token Objects: An Introduction to Elementary Object Nets” (ICATPN’98), Lecture Notes In Computer Science, 1420 (1998), 1-25.Valk R., “Petri Nets as Token Objects: An Introduction to Elementary Object Nets” (ICATPN’98), Lecture Notes In Computer Science, 1420 (1998), 1-25.

The authors declare that there are no conflicts of interest present.