О пространственной ограниченности клеточных Р-сетей
Аннотация
Клеточные Р-сети — обобщение концепции двухуровневых ресурсных сетей (сетей Петри) на случай бесконечной регулярной системной решетки. Этот формализм представляет собой гибрид сетей Петри и асинхронных клеточных автоматов и предназначен для моделирования мультиагентных систем с динамической пространственной структурой. Пространственная ограниченность — свойство, гарантирующее сохранение конечности “геометрических размеров” (например, площади) активной части системы на протяжении всей её жизни. Определяются три варианта пространственной ограниченности для клеточных Р-сетей: локализованность, ограниченность диаметра и ограниченность площади. Исследуются свойства соответствующих алгоритмических проблем, доказывается их неразрешимость в общем случае. Предлагается нетривиальный критерий локализованности одномерной клеточной сети, основанный на новой концепции графа распространения Р-автоматов. Описывается алгоритм построения графа распространения, использующий метод насыщения генерирующих путей. Предлагается способ оценки сверху диаметра одномерной клеточной сети с ограниченным графом распространения.
Ключевые слова
мультиагентные системы,
верификация,
сети Петри,
клеточные автоматы,
Р-сети,
пространственная ограниченность
Об авторе
Владимир Анатольевич Башкин
Ярославский государственный университет им. П.Г. Демидова
Россия
д-р физ.-мат. наук, доцент
Россия
д-р физ.-мат. наук, доцент
Список литературы
1. Башкин В. А., “Сети активных ресурсов”, Моделирование и анализ информационных систем, 14:4 (2007), 13-19
2. Башкин В. А., “Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов”, Программирование, 36:4 (2010), 3-15
3. Зайцев Д. А., “Верификация вычислительных решеток с особыми краевыми условиями бесконечными сетями Петри”, Моделирование и анализ информационных систем, 19:6 (2012), 21-33
4. Котов В. Е., Сети Петри, Наука, М., 1984
5. Кузьмин Е. В., Чалый Д.Ю., “О разрешимости проблем ограниченности для счетчиковых машин Минского”, Моделирование и анализ информационных систем, 15:1 (2008), 16-26
6. Alur R., Dill D., “Automata for modeling real-time systems” (Automata, Languages and Programming), Lecture Notes In Computer Science, 443 (1990), 322-335.
7. Bashkin V. A., “Nets of active resources for distributed systems modeling”, Joint Bulletin of NCC&IIS, Comp. Science, 28 (2008), 43-54.
8. Bashkin V. A., Lomazova I. A., “Resource Driven Automata Nets”, Fundamenta Informaticae, 109:3 (2011), 223-236.
9. Bashkin V. A., Lomazova I. A., “Cellular Resource Driven Automata Nets”, Fundamenta Informaticae, 120:3-4 (2012), 245-259.
10. 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.
11. 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.
12. Cook M., “Universality in Elementary Cellular Automata.”, Complex Systems, 15:1 (2004), 1-40.
13. Finkel A., Schnoebelen Ph., “Well-Structured Transition Systems Everywhere!”, Theoretical Computer Science, 256:1-2 (2001), 63-92.
14. Jensen K., Colored Petri Nets: Basic Concepts, Analysis Methods and Practical Use, Springer, 1994.
15. K¨ohler-Bußmeier M., “Hornets: Nets within Nets combined with Net Algebra” (ICATPN’2009), Lecture Notes In Computer Science, 5606 (2009), 243-262.
16. 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.
17. Nehaniv C. L., “Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network”, Int. J. of Algebra and Computation, 14:5-6 (2004), 719-739.
18. Petri C. A., Kommunikation mit Automaten. PhD thesis, Bonn Institute f¨ur Instrumentelle Mathematik, 1962.
19. Valk R., “Petri Nets as Token Objects: An Introduction to Elementary Object Nets” (ICATPN’98), Lecture Notes In Computer Science, 1420 (1998), 1-25.
Для цитирования:
Башкин В.А. О пространственной ограниченности клеточных Р-сетей. Моделирование и анализ информационных систем. 2017;24(4):391-409. https://doi.org/10.18255/1818-1015-2017-4-391-409
For citation:
Bashkin V.A. On the Spatial Boundedness of Cellular RDA-nets. Modeling and Analysis of Information Systems. 2017;24(4):391-409. (In Russ.) https://doi.org/10.18255/1818-1015-2017-4-391-409
Просмотров: 352
Послать статью по эл. почте 