Trace Nets and Conflict-free Computations

• Autorzy: Ochmański E. , Pieckowska J.
• Języki publikacji: EN

Abstrakty

EN

Trace nets are a generalization of elementary nets, proposed by Badouel and Darondeau. They admit phenomena, unknown in traditional nets. For instance, in trace nets does not hold the "diamond property". For this reason, we propose a more precise definition of conflict, applicable to trace nets, and study occurrences of conflicts and existence of conflict-free runs in such nets. Main result of the paper says that any just computation in a trace net, starting from a conflict state, contains a conflict step. This result allows to construct an algorithm, selecting only conflict-free just computations from among all computations of a given net. All results of the paper hold for elementary nets, as they are a subclass of trace nets.

Słowa kluczowe

EN

Petri net; trace nets; conflicts

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 72, nr 1-3
• Strony: 311--321
• Opis fizyczny: tab., wykr., bibliogr. 6 poz.

Twórcy

autor

Ochmański E.

autor

Pieckowska J.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• [1] Badouel, E., Darondeau, Ph.: Trace nets and process automata. Acta Informatica, 32, 1995, 647-679.
• [2] Busi, N., Gorrieri, R.: Positive Non-interference in Elementary and Trace Nets. LNCS, 3099, 2004, 1-16.
• [3] Desel, J., Reisig, W.: Place/Transition Petri Nets. LNCS, 1491, Springer, 1998, 122-173.
• [4] Lehman, D., Pnueli A., Stavi, J.: Impartiality, Justice and Fairness: the Ethics of Concurrent Termination. LNCS, 115, 1981, 264-277.
• [5] Reisig, W., Rozenberg, G.: Lectures on Petri Nets. LNCS 1491, Springer, 1998.
• [6] Rozenberg, G., Engelfriet, J.: Elementary Net Systems. LNCS, 1491, Springer, 1998, 12-121.