Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Reasoning About Discovery Clouds Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

The Power of Prime Cycles

verfasst von : Eike Best, Raymond Devillers

Erschienen in: Application and Theory of Petri Nets and Concurrency

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we shall examine properties of labelled transition systems which are motivated by system synthesis. Most of them are necessary conditions for synthesis by Petri nets to be successful. They can be checked in a pre-synthesis phase, allowing the immediate rejection of transition systems not satisfying them as non-synthesisable. The order of checking such conditions plays an important role in pre-synthesis optimisation. It is particularly desirable to know which conditions are implied by others, especially if the latter can be machine-verified more simply than the former. The purpose of this paper is to describe some mathematical results exhibiting a number of such implications.
Two properties called strong cycle-consistency and full backward determinism, respectively, are particularly hard to check. They are generalised counterparts of the marking equation of Petri net theory. We show that under some circumstances, they may be deduced from other properties which are easier to check. Amongst these other properties, the prime cycle property plays a particularly important role, not just because it is strong enough to imply others, but also because it is interesting to be checked on its own, if synthesis is targetted towards choice-free Petri nets.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Characterising Petri Net Solvable Binary Words
Nächstes Kapitel Petri Net Synthesis for Restricted Classes of Nets
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This algorithm has a complexity of \(O(n{\cdot }e{\cdot }\gamma )\) where n is the number of nodes of a graph, e the number of edges, and \(\gamma \) the number of small cycles. Thus, in our context, a bad upper bound is \(O(n^3{\cdot }m)\) where \(n=|S|\) and \(m=|T|\), which, however, still compares favourably with \(O(n^6)\) for the full synthesis algorithm.
 
2
Since, in brute force form, they involve, for all states \(s\in S\), Parikh-comparisons of pairs of – possibly long – paths emanating from s.
 
Literatur
1.
Badouel, É., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2015). ISBN 978-3-662-47967-4, 339 ppCrossRefMATH
2.
Badouel, É., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theor. Comput. Sci. 186(1–2), 107–134 (1997)MathSciNetCrossRefMATH
3.
Badouel, É., Darondeau, P.: Theory of regions. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models. LNCS, vol. 1491, pp. 529–586. Springer, Heidelberg (1999)CrossRef
4.
Badouel, É., Caillaud, B., Darondeau, P.: Distributing finite automata through Petri net synthesis. J. Formal Aspects Comput. 13, 447–470 (2002)CrossRefMATH
5.
Barylska, K., Best, E., Erofeev, E., Mikulski, Ł., Piątkowski, M.: On binary words being Petri net solvable. In: Carmona, J., Bergenthum, R., van der Aalst, W. (eds.) ATAED 2015, pp. 1–15. http://​ceur-ws.​org/​Vol-1371
6.
Best, E., Darondeau, P.: A decomposition theorem for finite persistent transition systems. Acta Informatica 46, 237–254 (2009)MathSciNetCrossRefMATH
7.
Best, E., Darondeau, P.: Petri net distributability. In: Virbitskaite, I., Voronkov, A. (eds.) PSI 2011. LNCS, vol. 7162, pp. 1–18. Springer, Heidelberg (2011)
8.
Best, E., Devillers, R.: Characterisation of the state spaces of live and bounded marked graph Petri nets. In: Dediu, A.H., Martín-Vide, C., Sierra-Rodríguez, J.L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 161–172. Springer, Heidelberg (2014)CrossRefMATH
9.
Best, E., Devillers, R.: Synthesis of bounded choice-free Petri nets. In: Aceto, L., Frutos Escrig, D. (eds.) Proceedings of the 26th International Conference on Concurrency Theory (CONCUR 2015), LIPICS, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 128–141 (2015). doi:10.​4230/​LIPIcs.​CONCUR.​2015.​128
10.
Best, E., Devillers, R.: Characterisation of the State Spaces of Marked Graph Petri Nets. Accepted for publication in Information and Computation (2015). 20 pp., Extended version of [8]
11.
12.
13.
14.
Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers. IEICE Trans. Inf. Syst. 80(3), 315–325 (1997)
15.
Darondeau, P.: Unbounded Petri net synthesis. In: Desel, J., Reisig, W., Rozenberg, G. (eds.) Lectures on Concurrency and Petri Nets. LNCS, pp. 413–438. Springer, Heidelberg (2004)CrossRefMATH
16.
Ehrenfeucht, A., Rozenberg, G.: Partial 2-structures, Part I: basic notions and the representation problem, and Part II: state spaces of concurrent systems. Acta Informatica 27(4), 315–368 (1990)MathSciNetCrossRefMATH
17.
van Glabbeek, R.J., Goltz, U., Schicke-Uffmann, J.-W.: On distributability of Petri nets - (Extended Abstract). In: Birkedal, L. (ed.) Foundations of Software Science and Computational Structures. LNCS, vol. 7213, pp. 331–345. Springer, Heidelberg (2012)CrossRefMATH
18.
Hopkins, R.P.: Distributable nets. In: Rozenberg, G. (ed.) Advances of Petri Nets 1991. LNCS, vol. 524, pp. 161–187. Springer, Heidelberg (1991). Applications and Theory of Petri Nets 1990CrossRef
19.
20.
Júlvez, J., Recalde, L., Silva, M.: Deadlock-freeness analysis of continuous mono-T-semiflow Petri nets. IEEE Trans. Autom. Control 51–9, 1472–1481 (2006)MathSciNetCrossRefMATH
21.
Keller, R.M.: A fundamental theorem of asynchronous parallel computation. In: Feng, T.Y. (ed.) Parallel Processing, pp. 102–112. Springer, Heidelberg (1975)CrossRef
22.
Kondratyev, A., Cortadella, J., Kishinevsky, M., Pastor, E., Roig, O., Yakovlev, A.: Checking signal transition graph implementability by symbolic BDD traversal. In: Proceedings of the European Design and Test Conference, Paris, France, pp. 325–332 (1995)
23.
Reisig, W.: Petri Nets. Monographs in Theoretical Computer Science. An EATCS Series, vol. 4. Springer, Heidelberg (1985)CrossRefMATH
24.
25.
Teruel, E., Colom, J.M., Silva, M.: Choice-free Petri nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Trans. Syst. Man Cybern. Part A 27–1, 73–83 (1997)CrossRef
Metadaten
Titel
The Power of Prime Cycles
verfasst von
Eike Best
Raymond Devillers
Copyright-Jahr
2016
Buch
Application and Theory of Petri Nets and Concurrency

Print ISBN: 978-3-319-39085-7

Electronic ISBN: 978-3-319-39086-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-39086-4_5

Premium Partner

    Bildnachweise