The Recognition Algorithm Design For Languages Of Bounded Petri Net

As modeling and analysis tools of distributed systems, Petri nets are applied more and more widely. The transitions firing sequences can specify the behaviors of the Petri nets. The Petri nets languages can be thought as a set composed by transitions firing sequences that can be accepted by the Petri net. So far, some relatively perfect research solutions of Petri nets languages have been given by the researchers at home and abroad, but most of them just use Petri nets as language generators, and there is few of them recognize the possibility of Petri nets as language recognizers.According to this status, this thesis does some discussions and tries on three different kinds of language recognition methods.Firstly, we divide S-net, a kind of structure-simple and behaviors easily specifying Petri net, into four classification; and specialize the running situation of Petri net into the running of automaton on the basis of equivalency of finite automaton and reachability graph of Petri net, then we give a algorithm of the construction of a finite automaton that can be used to recognize the languages of a bounded Petri net. By doing some process on those four kinds of S-net, we propose the language recognition algorithms of every kind of S-net and also time complexities of these algorithms are discussed.Secondly, two serial languages recognition algorithms of the bounded Petri net are given. They are a language recognition algorithm based on vector and a languages recognition algorithm based on finite automaton. First, we introduce a bounded Petri net language recognition algorithm and analyze the time complexity of the algorithm by using the method of the recognition of S-nets. Then transform the running of Petri net into vectors computation by which we introduce another bounded Petri net language recognition algorithm.Thirdly, a parallel languages recognition algorithm based on the polynomial-time decomposition of the bounded Petri net based on indexes of places. Because there may be state explosion problems on structure-complicated Petri nets, we introduce a modified decomposition method based on indexes of places, and propose a parallel recognition algorithm based on the indexes of places. Finally, the analyses of the time complexity of those algorithms are given.