Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: reduced state space generation

Sortuj według:

Ogranicz wyniki do:

Properties and analysis of [alfa]-nets

Karatkevich A

Informatyka Teoretyczna i Stosowana

2005

R. 5, nr 8

53-64

A restricted class of Petri nets equivalent to [alfa]-nets - the extended free choice nets with single-token initial marking - is considered, which corresponds to structnre of paralleI aotomata and parallel logical control algorithms. For nets of this class the dependence between such behavioural properties as liveness, safeness and reversibility is studied. It is shown that a net belonging to that class is live and sale if and only if it is reversible and the net graph is strongly connected. Sofie other results are proven on relation among reversibility and other net properties. Based on the obtained results, applying one of the reduced state space generation methods known as the stubborn set method to [alfa]-nets is considered. It is shown, that redoced reachability graph obtained by the method for such net allows to check whether the net is well-formed (live and sale); soch graph may be much smaller than the complete reachability graph of the net. Experimental results are presented.

Dla podklasy sieci Petriego, ekwiwalentnej [alfa]-sieciom - rozszerzonym sieciom swobodnego wyboru z jednym znacznikiem w znakowaniu początkowym - bada się zależność między niektórymi istotnymi własnościami behawioralnymi. Pokazane, że sieć, należąca do tej klasy, jest żywą i bezpieczną wtedy i tylko wtedy, gdy jest ona powtarzalna i silnie spójna. Przedstawione są niektóre inne rezultaty, związane z zależnościami między powtarzalnością i innymi własnościami sieci. Na podstawie otrzymanych rezultatów rozważa się zastosowanie metody upartych zbiorów (stubborn set method) do [alfa]-sieci; pokazane, że zbudowany za pomocą tej metody częściowy graf osiągalności dla takiej sieci zawiera informacje, pozwalającą sprawdzić, czy sieć jest "dobrze zbudowana" (żywa i bezpieczna).

Stable models for stubborn sets

Varpaaniemi K.

Fundamenta Informaticae

2000

Vol. 43, Nr 1-4

355-375

The stubborn set method is one of the methods that try to relieve the state space explosion problem that occurs in state space generation. Spending some time in looking for "good'" stubborn sets can pay off in the total time spent in generating a reduced state space. This article shows how the method can exploit tools that solve certain problems of logic programs. The restriction of a definition of stubbornness to a given state can be translated into a variable-free logic program. When a stubborn set satisfying additional constraints is wanted, the additional constraints should be translated, too. It is easy to make the translation in such a way that each acceptable stubborn set of the state is represented by at least one stable model of the program, each stable model of the program represents at least one acceptable stubborn set of the state, and for each pair in the representation relation, the number of certain atoms in the stable model is equal to the number of enabled transitions of the represented stubborn set. So, in order to find a stubborn set which is good w.r.t. the number of enabled transitions, it suffices to find a stable model which is good w.r.t. the number of certain atoms. The article also presents a new NP-completeness result concerning stubborn sets.