Time Petri nets state space reduction using dynamic programming

• Autorzy: Popova-Zeugmann L.
• Języki publikacji: EN

Abstrakty

EN

In this paper a parametric description for the state space of an arbitrary TPN is given. An enumerative procedure for reducing the state space is introduced. The reduction is defined as a truncated multistage decision problem and solved recursively. A reachability graph is denned in a discrete way by using the reachable integer-states of the TPN.

Słowa kluczowe

EN

time Petri net; dynamic programming; state space reduction; integer state; reachability graph

PL

programowanie dynamiczne

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 721--748
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Popova-Zeugmann L.

• Department of Computer Science, Humboldt-Universitat zu Berlin, Unter den Linden 6, 10099 Berlin, Germany,

Bibliografia

• BELLMAN, R. (1957) Dynamic Programming. Princeton Univ. Press, Princeton, New Jersey.
• BERTHOMIEU, B. and DIAZ, M. (1991) Modeling and Verification of Time Dependent Systems Using Time Petri Nets. IEEE Trans, on Software Eng. 17 (3), 259-273.
• BERTHOMIEU, B. and MENASCHE, M. (1983) An Enumerative Approach for Analyzing Time Petri Nets. In: IFIP Congress Series 9, Elsevier Science Publ. Comp., North Holland, 41-46.
• BERTSEKAS, D.P. (2000) Dynamic Programming and Optimal Control, Vol. I, 2nd edition. Athena Scient., Belmont, Mass.
• BOUCHENEB, H. and BERTHELOT, G. (1993) Towards a Simplified Building of Time Petri Net Reachability Graphs. In: Proceedings of Petri Nets and Performance Models PNPM 93, Toulouse, France, IEEE Computer Society Press.
• CASSEZ, F. and Roux, O.H. (2004) Structural Translation from Time Petri Nets to Timed Automata. In: Fourth International Workshop on Automated Verification of Critical Systems (AvoCS’04). Electronic Notes in Theoretical Computer Science, London (UK), Elsevier.
• EBBINGHAUS, H.-D., FLUMM, J. and THOMAS, W. (1994) Mathematical Logic. Springer-Verlag, New York-Berlin-Heidelberg.
• MERLIN. P.M. (1974) A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Computer Science Dept., Irvine.
• PENCZEK, W. (2000) Partial Order Reductions for Checking Branching Properties of Time Petri Nets. Proc. of the Int. Workshop on CS&P’00 Workshop, Informatik-Berichte 140 (2), 189-202.
• POPOVA-ZEUGMANN, L. (1989) Zeit-Petri-Netze. PhD thesis, Humboldt-Universität zu Berlin.
• POPOVA, L. (1991) On Time Petri Nets. J. Inform. Process. Cybern. EIK 27 (4), 227-244.
• POPOVA-ZEUGMANN, L. and SCHLATTER, D. (1999) Analyzing Path in Time Petri Nets. Fundamenta Informaticae 37, 311-327.
• POPOVA-ZEUGMANN, L. and WERNER, M. (2005) Extreme runtimes of schedules modelled by time petri nets. Fundamenta Informaticae 67, 163 174.
• SNIEDOVICH, M. (1992) Dynamic Programming. Marcel Dekker. New York.
• YEE, S.T. and VENTURA, J.A. (1999) A dynamic programming algorithm to determine optimal assembly sequences using petri nets. International Journal of Industrial Engineering - Theory, Applications and Practice 6 (1), 27-37.