О пространственной ограниченности клеточных Р-сетей

Владимир Анатольевич Башкин

doi:10.18255/1818-1015-2017-4-391-409

О пространственной ограниченности клеточных Р-сетей

Владимир Анатольевич Башкин

https://doi.org/10.18255/1818-1015-2017-4-391-409

Полный текст:

Аннотация

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

Ключ. слова

мультиагентные системы, верификация, сети Петри, клеточные автоматы, Р-сети, пространственная ограниченность,

Об авторе

Владимир Анатольевич Башкин

Ярославский государственный университет им. П.Г. Демидова
Россия
д-р физ.-мат. наук, доцент

Список литературы

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

Обратные ссылки

Обратные ссылки не определены.

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)

Логин
Пароль