Reachability in contextual nets

• Autorzy: Winkowski J.

Warianty tytułu

EN

Osiągalność w sieciach kontekstowych

• Języki publikacji: PL

Abstrakty

PL

Sieci kontekstowe, albo inaczej sieci Petriego z krawędziami odczytu, są modelami systemów współbieżnych z akcjami zależnymi od kontekstu. Problem osiągalności w takich sieciach polega na znalezieniu ciągu akcji prowadzącego od oznakowania początkowego danej sieci kontekstowej do zadanego oznakowania docelowego. Zaprezentowane w pracy rozwiązanie tego problemu polega na konstruowaniu skończonego zupełnego prefiksu rozwinięcia danej sieci kontekstowej, tzn. skończonego prefiksu, w którym są obecne wszystkie oznakowania osiągalne z oznakowania początkowego, oraz na poszukiwaniu w każdej gałęzi tego prefiksu oznakowania docelowego przez rozwiązywanie odpowiedniego problemu programowania liniowego.

EN

Contextual nets, or Petri nets with read arcs, are models of concurrent systems with context dependent actions. The problem of reachability in such nets consist in finding a sequence of transitions that leads from the initial marking of a given contextual net to a given goal marking. The solution to this problem that is presented in this paper consists in constructing a finite complete prefix of the unfolding of the given contextual net, that is a finite prefix in which all the markings that are reachable from the initial marking are present, and in searching in each branch of this prefix for the goal marking by solving an appropriate linear programming problem.

Słowa kluczowe

PL

sieć kontekstowa; sieci Petriego; kontekstowa sieć wystąpień; programowanie liniowe

EN

contextual net; Petri nets; contextual occurence net; linear programming

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2001
• Tom: Nr 926
• Strony: 1--15

Twórcy

autor

Winkowski J.

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