Discrete Parameters in Petri Nets

作者: Nicolas David , Claude Jard , Didier Lime , Olivier H. Roux

DOI: 10.1007/978-3-319-19488-2_7

关键词: Property (philosophy)USableCombinatoricsDecidabilityUndecidable problemDiscrete mathematicsValue (mathematics)Computer sciencePetri net

摘要: With the aim of significantly increasing modeling capability Petri nets, we suggest that models involve parameters to represent weights arcs, or number tokens in places. We consider property coverability markings. Two general questions arise: “Is there a parameter value for which is satisfied?" and “Does hold all possible values parameters?". show these issues are undecidable case. Therefore, also define subclasses parameterised networks, depending on whether used places, input output arcs transitions. For some subclasses, prove certain problems become decidable, making more usable practice.

参考文章(12)
C. Dufourd, A. Finkel, Ph. Schnoebelen, Reset Nets Between Decidability and Undecidability international colloquium on automata languages and programming. pp. 103- 115 ,(1998) , 10.1007/BFB0055044
Ernst W. Mayr, An algorithm for the general Petri net reachability problem Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 238- 246 ,(1981) , 10.1145/800076.802477
Rajeev Alur, Thomas A. Henzinger, Moshe Y. Vardi, Parametric real-time reasoning Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 592- 601 ,(1993) , 10.1145/167088.167242
G. Chiola, C. Dutheillet, G. Franceschinis, S. Haddad, A symbolic reachability graph for coloured petri nets Theoretical Computer Science. ,vol. 176, pp. 39- 65 ,(1997) , 10.1016/S0304-3975(96)00010-2
Neil D. Jones, Lawrence H. Landweber, Y. Edmund Lien, Complexity of some problems in Petri nets Theoretical Computer Science. ,vol. 4, pp. 277- 299 ,(1977) , 10.1016/0304-3975(77)90014-7
Toshiro Araki, Tadao Kasami, Some decision problems related to the reachability problem for Petri nets Theoretical Computer Science. ,vol. 3, pp. 85- 104 ,(1976) , 10.1016/0304-3975(76)90067-0
Richard M. Karp, Raymond E. Miller, Parallel program schemata Journal of Computer and System Sciences. ,vol. 3, pp. 147- 195 ,(1969) , 10.1016/S0022-0000(69)80011-5
Markus Lindqvist, Parameterized reachability trees for predicate/transition nets applications and theory of petri nets. pp. 1- 120 ,(1991) , 10.1007/3-540-56689-9_49
T. Touili, M. Nilsson, A. Bouajjani, B. Jonsson, Regular model checking Lecture Notes in Computer Science. pp. 403- 418 ,(2000)