On conflict-free executions of elementary nets

• Autorzy: Ochmański, E.

Warianty tytułu

PL

O bezkonfliktowym działaniu sieci elementarnych

• Języki publikacji: EN

Abstrakty

EN

The paper deals with analysis of elementary Petri nets with respect to possibilities of avoiding conflicts during their executions. In concurrent systems, unlike to the sequential ones, avoiding of potential conflicts is not impossible. The basic notion of the paper is the notion of fairness, in sequential (fair run) and concurrent (fair process) versions. Main results: 1. The proof of decidability, for elementary nets, of problem of existence of a conflict-avoidable fair process (and an algorithm producing all fair runs) and 2. Construction, for arbitrary given elementary net, a conflict-avoidable net with the same behaviour.

PL

Tematem pracy jest analiza elementarnych sieci Petriego pod katem mozliwości unikania sytuacji konfliktowych w trakcie ich działania. W systemach współbieżnych, w odróżnieniu od sekwencyjnych, unikanie potencjalnych konfliktów nie jest niemożliwe. Podstawowym pojęciem jest pojęcie uczciwości (fairness), zarówno w wersji sekwencyjnej (uczciwy przebieg liniowy), jak i współbieżnej (uczciwy proces). Najważniejsze wyniki pracy to: 1. Dowód rozstrzygalności problemu istnienia dla danej sieci elementarnej, bezkonfliktowego procesu uczciwego (wraz z algorytmem produkującym wszystkie uczciwe przebiegi) i 2. Konstrukcja dla dowolnej danej sieci elementarnej, sieci potencjalnie bezkonfliktowej o tym samym zachowaniu.

• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2000
• Tom: nr 921
• Strony: 1-12

Twórcy

autor

Ochmański, E.

• Instytut Podstaw Informatyki PAN ul. Ordona 21 01-237 Warszawa,