Top

Published in:

2019 | OriginalPaper | Chapter

Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems: A Geometric Approach

Authors : Raymond Devillers, Evgeny Erofeev, Thomas Hujsa

Published in: Transactions on Petri Nets and Other Models of Concurrency XIV

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recent studies investigated the problems of analysing Petri nets and synthesising them from labelled transition systems (LTS) with two labels (transitions) only. In this paper, we extend these works by providing new conditions for the synthesis of Weighted Marked Graphs (WMGs), a well-known and useful class of weighted Petri nets in which each place has at most one input and one output.

Some of these new conditions do not restrict the number of labels; the other ones consider up to 3 labels. Additional constraints are investigated: when the LTS is either finite or infinite, and either cyclic or acyclic. We show that one of these conditions, developed for 3 labels, does not extend to 4 nor to 5 labels. Also, we tackle geometrically the WMG-solvability of finite, acyclic LTS with any number of labels.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Kleene Theorems for Free Choice Automata over Distributed Alphabets

next chapter Evaluating Conformance Measures in Process Mining Using Conformance Propositions

A set A of k arcs in a LTS G defines a cycle of G if the elements of A can be ordered as a sequence \(a_1 \ldots a_k\) such that, for each \(i \in \{1, \ldots , k\}\), \(a_i = (n_i,\ell _i,n_{i+1})\) and \(n_{k+1} = n_1\), i.e. the i-th arc \(a_i\) goes from node \(n_i\) to node \(n_{i+1}\) until the first node \(n_1\) is reached, closing the path. Cycles are also sometimes called circuits, circles and oriented cycles.

The projection of a word \(w\in A^*\) on a set \(A' \subseteq A\) of labels is the maximum subword of w whose labels belong to \(A'\), noted

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-60651-3_7/492321_1_En_7_IEq373_HTML.gif

. For example, the projection of the word \(w = \ell _1 \, \ell _2 \, \ell _3 \, \ell _2\) on the set \(\{\ell _1 ,\, \ell _2\}\) is the word \(\ell _1 \, \ell _2 \, \ell _2\).

Also called sometimes the synchronisation on transitions.

Murata, T.: Petri nets: properties, analysis and applications. Proc. IEEE 77(4), 541–580 (1989)CrossRef

Teruel, E., Silva, M.: Structure theory of equal conflict systems. Theoret. Comput. Sci. 153(1&2), 271–300 (1996)MathSciNetCrossRef

Hujsa, T., Devillers, R.: On liveness and deadlockability in subclasses of weighted Petri nets. In: van der Aalst, W., Best, E. (eds.) PETRI NETS 2017. LNCS, vol. 10258, pp. 267–287. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57861-3_16CrossRefMATH

Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science, vol. 40. Cambridge University Press, New York (1995)CrossRef

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

Hujsa, T., Delosme, J.-M., Munier-Kordon, A.: On the reversibility of well-behaved weighted choice-free systems. In: Ciardo, G., Kindler, E. (eds.) PETRI NETS 2014. LNCS, vol. 8489, pp. 334–353. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07734-5_18CrossRefMATH

Commoner, F., Holt, A., Even, S., Pnueli, A.: Marked directed graphs. J. Comput. Syst. Sci. 5(5), 511–523 (1971)MathSciNetCrossRef

Teruel, E., Chrzastowski-Wachtel, P., Colom, J.M., Silva, M.: On weighted T-systems. In: Jensen, K. (ed.) ICATPN 1992. LNCS, vol. 616, pp. 348–367. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55676-1_20CrossRef

Best, E., Hujsa, T., Wimmel, H.: Sufficient conditions for the marked graph realisability of labelled transition systems. Theoret. Comput. Sci. 750, 101–116 (2017)MathSciNetCrossRef

10.

Devillers, R., Hujsa, T.: Analysis and synthesis of weighted marked graph Petri nets. In: Khomenko, V., Roux, O.H. (eds.) PETRI NETS 2018. LNCS, vol. 10877, pp. 19–39. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91268-4_2CrossRefMATH

11.

Delosme, J.M., Hujsa, T., Munier-Kordon, A.: Polynomial sufficient conditions of well-behavedness for weighted join-free and choice-free systems. In: 13th International Conference on Application of Concurrency to System Design, pp. 90–99, July 2013

12.

Hujsa, T., Delosme, J.M., Munier-Kordon, A.: Polynomial sufficient conditions of well-behavedness and home markings in subclasses of weighted Petri nets. ACM Trans. Embed. Comput. Syst. 13(4s), 141:1–141:25 (2014)CrossRef

13.

Barylska, K., Best, E., Erofeev, E., Mikulski, L., Piatkowski, M.: On binary words being Petri net solvable. In: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data, ATAED 2015, Brussels, Belgium, pp. 1–15 (2015)

14.

Barylska, K., Best, E., Erofeev, E., Mikulski, L., Piatkowski, M.: Conditions for Petri net solvable binary words. Trans. Petri Nets Other Models Concurr. 11, 137–159 (2016)MathSciNetMATH

15.

Erofeev, E., Barylska, K., Mikulski, L., Piatkowski, M.: Generating all minimal Petri net unsolvable binary words. In: Proceedings of the Prague Stringology Conference 2016, Prague, Czech Republic, pp. 33–46 (2016)

16.

Erofeev, E., Wimmel, H.: Reachability graphs of two-transition Petri nets. In: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2017, Zaragoza, Spain, pp. 39–54 (2017)

17.

Best, E., Devillers, R.: Synthesis and reengineering of persistent systems. Acta Inf. 52(1), 35–60 (2015)MathSciNetCrossRef

18.

Hujsa, T., Delosme, J.M., Munier-Kordon, A.: On liveness and reversibility of equal-conflict Petri nets. Fundamenta Informaticae 146(1), 83–119 (2016)MathSciNetCrossRef

19.

Hujsa, T.: Contribution to the study of weighted Petri nets. Ph.D. thesis, Pierre and Marie Curie University, Paris, France (2014)

20.

Devillers, R., Erofeev, E., Hujsa, T.: Synthesis of weighted marked graphs from constrained labelled transition systems. In: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data, Bratislava, Slovakia, pp. 75–90 (2018)

21.

Crespi-Reghizzi, S., Mandrioli, D.: A decidability theorem for a class of vector-addition systems. Inf. Process. Lett. 3(3), 78–80 (1975)MathSciNetCrossRef

22.

Devillers, R.: Products of transition systems and additions of Petri nets. In: Desel, J., Yakovlev, A. (eds.) Proceedings of 16th International Conference on Application of Concurrency to System Design (ACSD 2016), pp. 65–73 (2016)

23.

Devillers, R.: Factorisation of transition systems. Acta Informatica 55, 339–362 (2017)MathSciNetCrossRef

24.

Best, E., Erofeev, E., Schlachter, U., Wimmel, H.: Characterising Petri net solvable binary words. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 39–58. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39086-4_4CrossRefMATH

25.

Doignon, J.P.: Convexity in cristallographical lattices. J. Geom. 3(1), 71–85 (1973)MathSciNetCrossRef

26.

Keller, R.M.: A fundamental theorem of asynchronous parallel computation. In: Feng, T. (ed.) Parallel Processing. LNCS, vol. 24, pp. 102–112. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07135-0_113CrossRef

27.

Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4CrossRefMATH

28.

David, R., Alla, H.: Discrete, Continuous, and Hybrid Petri Nets, 2nd edn. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-10669-9CrossRef

Title: Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems: A Geometric Approach
Authors: Raymond Devillers
Evgeny Erofeev
Thomas Hujsa
Publisher: Springer Berlin Heidelberg
Book: Transactions on Petri Nets and Other Models of Concurrency XIV
Print ISBN: 978-3-662-60650-6

Electronic ISBN: 978-3-662-60651-3

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-662-60651-3_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner