Наследcтвенные свойства модульных сетей
https://doi.org/10.18255/1818-1015-2012-6-9-20
Аннотация
Свойство графа называется наследственным, если каждый подграф также обладает этим свойством (например, планарность). Модульные сети активных ресурсов — формализм, эквивалентный по выразительной мощности сетям Петри, но при этом обладающий простым модульным синтаксисом. Ограниченность и живость — фундаментальные семантические свойства моделей, основанных на сетях Петри. Показано, что ограниченность и живость, не являясь наследственными свойствами в общем случае, становятся наследственными вниз (от сети к подсети) и наследственными вверх (от подсети к сети) для специальных типов АР-модулей. Также показано, что ограниченность наследуется вниз, а неограниченность наследуется вверх для произвольных модулей в сетях, подвергнутых достаточно простому и не нарушающему их поведение преобразованию интерфейсов модулей — процедуре Р-нормализации.
Об авторе
Владимир Анатольевич БашкинРоссия
канд. физ.-мат. наук, доцент кафедры теоретической информатики
Список литературы
1. Башкин В.А. Сети активных ресурсов // Моделирование и анализ информационных систем. 2007. Т. 14, № 4. С. 13–19.
2. Башкин В.А. Формализация семантики систем с ненадежными агентами при помощи сетей активных ресурсов // Программирование. 2010. № 4. С. 3 – 15.
3. Bashkin V.A., Lomazova I.A. Resource Driven Automata Nets // Fundamenta Informaticae. 2011. V. 109(3). P. 223–236.
4. Башкин В.А. Модульные сети активных ресурсов // Автоматика и вычислительная техника. 2012. №1. С. 5–18.
5. Best E., Devillers R., Koutny M. Petri Net Algebra // EATCS Monographs on TCS. Springer, Berlin, 2001.
6. Best E., Fr¸aczak W., Hopkins R.P., Klaudel H., Pelz E. M-nets: an algebra of high level Petri nets, with an application to the semantics of concurrent programming languages // Acta Inf. 1998. Vol. 35. P. 813–857.
7. Borowiecki M., Broere I., Frick M., Mihok P., Peter S. A survey of hereditary properties of graphs // Discuss. Mathem.: Graph Theory. 1997. Vol. 17. P. 5–50.
8. Christensen S., Petrucci L. Modular analysis of Petri nets // The Computer Journal. 2000. Vol. 43(3). P. 224–242.
9. Janˇcar P. Decidability questions for bisimilarity of Petri nets and some related problems // Proc. of STACS’94. 1994. LNCS 775. P. 581–592.
10. Kindler E. A compositional partial order semantics for Petri net components // Proc. of ATPN’1997. LNCS 1248. Springer, 1997. P. 235–252.
11. Klai K., Haddad S., Ili´e J.-M. Modular Verification of Petri Nets Properties: A Structure-Based Approach // Proc. of FORTE’2005. LNCS 3731. 2005. P. 189–203.
12. Котов В.Е. Сети Петри. М.: Наука, 1984.
13. Lomazova I.A. Nested Petri nets — a Formalism for Specification and Verification of Multi-Agent Distributed Systems // Fundamenta Informaticae. 2000. V. 43. P. 195–214.
14. Харари Ф. Теория графов. М.: Мир, 1973.
Рецензия
Для цитирования:
Башкин В.А. Наследcтвенные свойства модульных сетей. Моделирование и анализ информационных систем. 2012;19(6):9-20. https://doi.org/10.18255/1818-1015-2012-6-9-20
For citation:
Bashkin V.A. On the Hereditary Properties of Modular Nets. Modeling and Analysis of Information Systems. 2012;19(6):9-20. (In Russ.) https://doi.org/10.18255/1818-1015-2012-6-9-20