On the Hereditary Properties of Modular Nets
https://doi.org/10.18255/1818-1015-2012-6-9-20
Abstract
Hereditary graph properties are those that can be inherited from the graph to all its subgraphs (such as planarity). Modular nets of active resources is a (Petri nets)- powerful formalism with simple modular syntax. Boundedness and liveness are fundamental semantic properties for Petri net models. It is shown that boundedness and liveness, being not hereditary in general, are downward-hereditary (net-to-subnet) and upward-hereditary (subnet-to-net) for the particular types of AR-subnets. It is also shown that boundedness is downward-hereditary and unboundedness is upward-hereditary for arbitrary subnets after a specific module interface transformation (so-called R-normalization).
About the Author
V. A. Bashkin
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
канд. физ.-мат. наук, доцент кафедры теоретической информатики,
Sovetskaya str., 14, Yaroslavl, 150000, Russia
References
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.
Review
For citations:
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
Views:
929
Email this article 