Boolean Petri Nets
Sangita Kansal, Mukti Acharya, Gajendra Pratap · InTech eBooks · 2012
Petri net is a graphical tool invented by Carl Adam Petri [13]. These are used for describing, designing and studying discrete event-driven dynamical systems that are characterized as being concurrent, asynchronous, distributed, parallel, random and/or nondeterministic. As a graphical tool, Petri net can be used for planning and designing a system with given objectives, more practically effective than flowcharts and block diagrams. As a mathematical tool, it enables one to set up state equations, algebraic equations and other mathematical models which govern the behavior of discrete dynamical systems. Still, there is a drawback inherent in representing discrete event-systems. They suffer from the state explosion problem as what will happen when a system is highly populated, i.e., initial state consists of a large number of places that are nonempty. This phenomenon may lead to an exponential growth of its reachability graph. This makes us to study the safe systems. The aim of this chapter is to present some basic results on 1-safe Petri nets that generate the elements of a Boolean hypercube as marking vectors. Complete Boolean hypercube is the most popular interconnection network with many attractive and well known properties such as regularity, symmetry, strong connectivity, embeddability, recursive construction, etc. For brevity, we shall call a 1-safe Petri net that generates all the binary n-vectors as marking vectors a Boolean Petri net. Boolean Petri nets are not only of theoretical interest but also are of practical importance, required in practice to construct control systems [1]. In this chapter, we will consider the problems of characterizing the class of Boolean Petri nets as also the class of crisp Boolean Petri nets, viz., the Boolean Petri nets that generate all the binary n-vectors exactly once. We show the existence of a disconnected Boolean Petri net whose reachability tree is homomorphic to the n-dimensional complete lattice Ln. Finally, we observe that characterizing a Boolean Petri net is rather intricate.