演講公告 91年3月27日 (星期三)

摘要

In spite of their popularity in modeling concurrent systems, Petri nets (or equivalently, vector addition systems) are one of the most intricate models with their computational power only `slightly weaker' than that of Turing machines. In the late seventies and early eighties, there was a vast amount of theoretical work reported in the literature regarding the decidability/complexity analysis of Petri nets. A number of key techniques have been devised for analyzing problems such as boundedness, liveness, reachability, language equivalence, among others, for general Petri nets as well as for various subclasses of Petri nets on which certain structural and/or behavioral constraints are imposed. These techniques and results lay the foundation for recent advances of Petri net theory in the areas of temporal logic and process algebra. In this talk, we survey a number of analytical techniques (including integer linear programming, Presburger arithmetic, well-quasi ordering, and more) in Petri net theory, and discuss the suitability of the conventional `tractable-intractable' classification in dealing with Petri net complexities. Recent developments regarding extended Petri nets will also be addressed from the computability viewpoint.