Hostname: page-component-8448b6f56d-m8qmq Total loading time: 0 Render date: 2024-04-16T10:44:22.277Z Has data issue: false hasContentIssue false
  • English
  • Français

Analyzing the dynamics of deterministic systems from a hypergraph theoretical point of view

Published online by Cambridge University Press:  03 September 2013

Luis M. Torres  and
Annegret K. Wagler
Luis M. Torres
Affiliation:
Research Center on Mathematical Modelling MODEMAT, Escuela Politécnica Nacional, Quito, Ecuador. luis.torres@epn.edu.ec
Annegret K. Wagler
Affiliation:
Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (LIMOS), Université Blaise Pascal, Clermont-Ferrand, France; Annegret.WAGLER@univ-bpclermont.fr
Get access

Abstract

To model the dynamics of discrete deterministic systems, we extend the Petri nets framework by a priority relation between conflicting transitions, which is encoded by orienting the edges of a transition conflict graph. The aim of this paper is to gain some insight into the structure of this conflict graph and to characterize a class of suitable orientations by an analysis in the context of hypergraph theory.

Keywords

Petri netsdeterministic dynamic systemshypergraphs
Type
Research Article
Information
RAIRO - Operations Research , Volume 47 , Issue 3 , July 2013 , pp. 321 - 330
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Acharya, B.D. and Las Vergnas,, M. Hypergraphs with cyclomatic number zero, triangulated hypergraphs and an inequality. J. Combin. Theory (B) 33 (1982) 52–56. Google Scholar
Adam, N.R., Atluri, V. and Huang, W.K., Modeling and analysis of workflows using Petri nets. J. Intell. Inf. Syst. 10 (1998) 131–158. Google Scholar
G. Balbo, Introducation to stochastic Petri nets, in Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Springer-Verlag New York, Inc., New York, NY, USA (2002) 84–155.
C. Berge and P. Duchet, A generalisation of Gilmore’s theorem, in Recent advances in graph theory, edited by M. Fiedler, Acad. Praha, Prague (1975) 49–55.
J. Billington, M. Diaz and G. Rozenberg, Application of Petri nets to communication networks, Advances in Petri Nets. Springer-Verlag, London, UK (1999)
R. David and H. Alla, Discrete, Continuous, and hybrid Petri nets. Springer-Verlag Berlin Heidelberg, Heidelberg (2005).
P. Duchet, Propriété de helly et problèmes de représentations, in Problèmes Combinatoires et Théorie des Graphes, Coll. Orsay 1976, CNRS Paris (1978) 117–118.
Flament, C., Hypergraphes arborés. Discrete Math. 21 (1978) 223–226. Google Scholar
Gu, T. and Bahri, P.A., A survey of Petri net applications in batch processes. Comput. Ind. 47 (2002) 99–111. Google Scholar
Hardy, S. and Robillard, P.N., Modeling and simulation of molecular biology systems using Petri nets: modeling goals of various approaches. J. Bioinform. Comput. Biol. 2 (2004) 619–637. Google Scholar
K.Jensen, Coloured Petri nets: basic concepts, analysis methods and practical use, vol. 3, Springer-Verlag New York, Inc., New York, NY, USA (1997)
I. Koch and M. Heiner, Petri nets, in Analysis of biological networks, edited by B.H. Junker and F. Schreiber, Wiley Book Series in Bioinformatics (2008) 139–180.
M. Marsan, G. Balbo, S. Donatelli, G. Franceschinis and G. Conte, Modelling with generalized stochastic Petri nets. Wiley Series in Parallel Computing (1995).
Marwan, W., Theory of time-resolved somatic complementation and its use for the analysis of the sporulation control network of Physarum polycephalum. Genetics 164 (2003) 105–115. Google ScholarPubMed
Marwan, W. and Starostzik, C., The sequence of regulatory events in the sporulation control network of Physarum polycephalum analysed by time-resolved somatic complementation of mutants. Protist 153 (2002) 391–400. Google ScholarPubMed
Marwan, W., Sujatha, A. and Starostzik, C., Reconstructing the regulatory network controlling commitment and sporulation in Physarum polycephalum based on hierarchical Petri net modeling and simulation. J. Theor. Biol. 236 (2005) 349–365. Google Scholar
Marwan, W., Wagler, A. and Weismantel, R., A mathematical approach to solve the network reconstruction problem. Math. Meth. Oper. Res. 67 (2008) 117–132. Google Scholar
W. Reisig, Petri nets: an introduction. Springer-Verlag New York, Inc., New York, NY, USA (1985).
W. Reisig, Elements of distributed algorithms: modeling and analysis with Petri nets. Springer-Verlag New York, Inc., New York, NY, USA (1998).
Slater, P.J., A characterization of soft hypergraphs. Canad. Math. Bull. 21 (1978) 335–337. Google Scholar
Torres, L.M. and Wagler, A., Model reconstruction for discrete deterministic systems. Electronic Notes of Discrete Mathematics 36 (2010) 175–182. Google Scholar
Torres, L.M. and Wagler, A., Encoding the dynamics of deterministic systems. Math. Methods Operations Res. 73 (2011) 281–300. Google Scholar
Yakovlev, A., Koelmans, A., Semenov, A. and Kinniment, D., Modelling, analysis and synthesis of asynchronous control circuits using Petri nets. Integr. VLSI J. 21 (1996) 143–170. Google Scholar