Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 2(5), 21-28, May (2013) Res.J.Recent Sci. International Science Congress Association 21 A Survey on Linear Algebraic Approaches for the Analysis of Petri Net based ModelsFarooq Ahmad1*, Sher Afzal Khan, Ilyas Fakhir and Yaser Daanial Khan1,2Faculty of Information Technology, University of Central Punjab Lahore, PAKISTAN Department of Computer Science, Abdul Wali Khan University Mardan, PAKISTAN 3 Department of Computer Science, GC University Lahore, PAKISTANAvailable online at: www.isca.in Received 28th November 2012, revised 27th December 2012, accepted 24th January 2013Abstract Petri net (PN) as a graphical and mathematical formalism has extensively been used for the modeling, control and analysis of discrete event systems and it has been recognized as flexible modeling technique because it is well suited for modeling the multifarious constraints. This paper focuses on the recent developments in the area of linear algebraic techniques for the PN models for systems. Theoretical developments in the area of PN based applications in the design and analysis of the systems with the practical experiences are discussed and further identified the research trends in this area. The transitive matrix and the transition vectors based applications are also overviewed for the first time in the literature. Keywords: Petri net, place/transition invariants, transitive matrix, transition vectors. IntroductionThe size and complexity of automated systems, e.g. distributed computer systems, reactive systems and distributed database systems, often require a number of processes containing distinct operations. Such systems can be called as supervised systems, in which supervisors are used to coordinate the operations of various subsystems so that overall system’s specification is definite. The design of discrete event supervisory controllers for the systems is important step to construct the intelligent control systems. In designing the system, in essence, it is important to know and be able to identify the required behavior of the controlled system. For this purpose it is necessary to use a formalism to specify the required behavior. Further, the controller is required to specify and analyze with the formalism and analysis of different kind of systems has been performed in the literature1-5. Thereafter, the final control program describing the operations of the system through a sequence of instructions is implemented and verified by the formalism applied. Petri net (PN) formalism is extensively used for the modeling, control, analysis and design of discrete event systems and it has been recognized as flexible modeling technique because it is well suited for modeling the diverse constraints. Due to its graphical representation, the PN model can be developed and enhanced from the logical sequencing of the system. Further, PN modeling incorporates concurrency non-determinism, timing information and resource-sharing7,8 and capture structural interactions to model deadlocks, conflicts, buffer-sizes and precedence relations. In addition, PNs have the salient feature to perform qualitative and quantitative analysis of the modeled system due to their underlying mathematical foundation. There are significant advantages of PNs with respect to other formalisms due to the following reasons. First, a PN state is a vector of non-negative integers, where the state space for automata is a symbolic unstructured set. Further, many analysis techniques (e.g., linear-algebraic techniques, net reduction and refinement methods, etc.) have been developed for PN based models which do not require the state space enumeration and related computation can be made by utilizing their structural information. In addition, PNs have the capacity to represent graphically and visualize the primitives whereas, automata can only describe the interleaving of events and not their simultaneous occurrence thus concurrency may not be represented through automata. PN models for FMSs also have advantages over their digraph models. In the digraph model of a system, vertices only represent the system resources. Whereas, PNs are bipartite digraphs whose places-type vertices represent the available and used resources and transitions describe the events representing changes in resource allocation. After performing the modeling of physical system, the main power of PNs as mathematical tool is its support for analysis to study the dynamic behavior. Generally, the analysis of PNs can be classified into the state space based methods and structural analysis including the net reduction and refinement10. The state space enumeration method which requires the construction of reachability graph11 is important and fundamental approach for verification and qualitative analysis of the PN model. Further, it provides complete and detailed information about the dynamic behavior of PN models. One of the main advantages of reachability graph method is that its application is not limited to a certain sub-class of PN. However, Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 22 the size of reachability graph for PN models is main hurdle to apply this method because its generation requires memory and time at least proportional to the number of reachable markings and it suffers from state explosion problem. Moreover, complete state enumeration is needed for state based analysis methods while the computational complexity has been a major problem when generating the state space for the PN model12. On the contrary, the linear algebraic methods for PN models has advantage over state space generation methods because the static structure of PN facilitates to study marking-independent properties which depend on the place-transition relationship of underlying net by the flow relation13. The underlying static structural has a potential to provide important information about the dynamic behavior of the modeled system. So the behavioral properties that are of foremost interest and less easily analyzable in the analysis of systems may be reduced to easier-to-investigate structural properties14. Therefore, linear algebraic approaches grasped the attention of the researchers and have been widely used for the analysis of PN based models. This paper reveals the major findings in theoretical as well as application perspective of such kind of techniques for the PN based systems and overviews the recent developments in this area. The paper is organized as follows. Section 1 was about introduction and purpose of this review. Section 2 is about the definitions and concepts about Petri nets and the review of basic linear algebraic methods. Application of structural invariant based techniques in the literature about PN analysis is discussed in section 3. Section 4 provides transitive matrix based applications to the structural analysis while section 5 throw light on the transition vector based application and some concluding remarks are given in section 6. Linear Algebraic Techniques in the Petri Nets: The linear algebraic techniques for PN are mainly based on incidence matrix11 which is the matrix representation of a PN and shows the relationship between the structure of net and its behavior15,16. Such matrix representation of a PN together with appropriate equation systems or systems of inequalities can be used for describing the properties of its behavior.Definition 1: (Petri net)11 A marked Petri net (Place/Transition Net) is a 5-tuple PN = (P, T, F, W, M where: P = {p, p, ….., p finite set of places for n�0, T = {t1, t, ……, finite set of transitions for m�0, F (P X T) (T X P) is a set of arcs (flow relation), W = F {1, 2, 3, …… } is the weight function, = P {0, 1, 2, 3, ….. } is the initial marking, P F = and P F A PN structure (P, T, F, W) is denoted by , so that a PN with specific initial marking is denoted by (N, M). Definition 2: (Input matrix, output matrix and incidence matrix) 6 A pure net N = (P,T,F,W) can be represented by its incidence matrix [N], where [N] is a |P|×|T| integer matrix with [N](p, t)=W(t, p) W(p, t). Further, the |P| |T| matrices [N] (p, t) = W(p, t) and [N]+ (p, t) = W(t, p) are called input (incidence) matrix and output (incidence) matrix, respectively. The incidence matrix [N] of a net is defined as [N] = [N] [N]. Let (N, M0) be a net system and s be a fireable sequence of transitions from M. The (integer) linear relaxation is given as: 00 [ [N].0,0 MMMMsss =+³³  Where M is reachable from M by firing s , s  is Parikh vector or firing vector of s and [N] is incidence matrix of a net . This is the state or fundamental equation of net system model 14, 15. Any reachable marking in a place/transition net fulfils the state equation however the converse is not true. In this sense, the state equation provides a necessary condition for a marking M to be reachable from an initial marking M. Videlicet, if marking M is reachable from M, the state equation must have a vector solution for s  with its components in N (set of natural numbers). Now by applying the linear algebraic technique with the help of incidence matrix, we can find the set of places in a net which do not change their token count by firing the transitions of the net. Such set of places in a net is called P-invariants. Invariants are important resources for analyzing the behavior of a place/transition net from its structure. Therefore, the most important structural question about the analysis of PNs is the determination of place and transition invariants. In the same way solving the system of linear equations, we can find the set of transitions known as T-invariant, the firing sequence of the transitions in T-invariant which is enabled in a marking, it leads again to this marking. Definition 3: (Place/transition invariant)12 A P-vector is a column vector : P Z indexed by P and a T-vector is a column vector : T Z indexed by T, where Z is the set of integers. P-vector I is called a P-invariant (place invariant) iff I 0 and . [N] = T . T-vector is called a T-invariant (transition invariant) iff J 0 and [N]. = . Where, is column vector having each entry equal to zero. Theorem 4: Let (N, M) be a net with P-invariant and M be a reachable marking from M. Then .M = . M0 12. Theorem 5: Let (N, M) be a net with a transition sequence s such that 0[ MM . Then M = M if and only if s  is a T-invariant of N 12. Definition 6: (Boundedness and safeness) 11, 14 for all pP Î of PN (N, M, PN is b-bounded if 0 () k MRM "Î : ()ki Mpb £ and said to be safe if ()1 kiMp £ . Moreover, a PN is said to be structurally bounded if it is bounded for any finite initial marking . Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 23 Definition 7: (Deadlock, deadlock-free and liveness)9,11 A transition tT Î is said to be dead transition at marking 0 () k MRM Î if there is no reachable marking to make transition j t enabled. A marking 0 () k MRM Î is said to be deadlock if tT "Î , j t is dead. A PN (N, M) is said to be deadlock-free if and only if there is no deadlock. A PN (N, M) is said to be live if there is no dead transition at any reachable marking. Applications of Invariant Based Techniques in the Literature of Petri NetanalysisMost of the PN models developed for control applications for the systems have been analyzed structurally by using the linear algebraic techniques which lead to invariant analysis method. Moreover, the structural properties of PNs have been successfully used for the design of supervisors for supervisory control problems17. The results in the literature mostly address the synthesis of discrete event controller which consists of avoidance of unwanted, bad or forbidden states given in a control specification. The use of PNs structural techniques in the supervisory control of discrete event systems has been presented by different authors and non-blocking property has been studied for the system’s behavior under supervision. The deadlock avoidance control policy using the structural analysis of bounded asymmetric choice nets called PAC net has been addressed. The authors introduced the control places added to the control model to avoid the global deadlock18. The authors consider a class of place/transition nets, called elementary composed state machines. The reachability problem for this class has been solved by a modification of classical incidence matrix analysis18. General properties of systems e.g. stability, place-invariant, and conservativeness have been presented by using the state-space formulation of the equations describing the dynamic behavior of systems modeled by continuous PNs19. Fundamental equations that govern the dynamic behavior have been provided for batches PN and defined the invariant concepts with the determination of the quantity vector, then used to analyze the structural properties of the batches PN20. A class of PNs based on primary components of flexible manufacturing systems introduced which allows for representing the unidirectional flow of physical resources and control information21. The work further addresses the issue of the verification of the interconnections or interfaces among the PN models of primary components by the introduction of functional abstractions of the PN models. The place invariant implied subnets has been introduced which can be used for evaluation of the basic performance characteristics of the Petri net models. Further, the relationship to the controllability and boundedness of PN models has been discussed by P-invariant analysis and it has been concluded that they cannot be fully controllable and bounded simultaneously22. A method has been proposed to model sequential control systems by using PNs with place invariance as well as a method of dividing a large PN model into some small sub nets using the same place invariance in Miyazawa et al.23. An approach has been proposed, based on firing sequence of a place/transition net as a use case, for the synthesis and analysis of a FMS while invariance-preserving transformations has been used to ensure the preservation of place and transition invariants during synthesis and simplification24. The Petri net controller by using redundant places, connections and tokens to impose invariant conditions has been introduced that allow the detection and identification of faults via linear parity checks25. The proposed redundant Petri net controller makes efficient use of redundancy and allows for the systematic detection and identification of faults. The research work of Kezic et al. uses a method for P-invariant based Petri net controller design for automatic traffic control of marine canal traffic system26. The authors describe a method for calculating control places which control conflicts and restrict the set of reachable states to avoid first and second level deadlocks. The invariant analysis for task refinement, a kind of workflow composition approach, of workflow nets has been presented and proposed a sufficient condition for 1- soundness of task refinement of workflow nets27. A method has been presented to reduce the number of constraints for safe and conservative PNs. The proposed method needed to construct the set of possible states, which was more expensive than the set of reachable states28. PNs based models have been used for the diagnosis of discrete event systems in the fault detection aspect and several researchers used the structural methods in this regard, e.g., place-invariant based method and modular based approach to build the diagnose. A diagnosis approach has been presented where the diagnoser was built on-line by defining and solving integer linear programming problems and diagnoser worked on-line to avoid the redesign of the diagnoser for the changed structure of the systems29. A method to design optimal control places and an iteration approach to obtain a maximally permissive liveness-enforcing supervisor for an FMS has been presented by Chen et al.30. A minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBM) has been computed by using a vector covering approach. A place invariant has also been designed to prevent the FBM from being reached by solving an integer linear programming problem. An invariant based method has been presented, for a class of nets SPR, to explore all the live lost states in the first-met bad marking (FBM) method, when an alternative control policy is employed31. Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 24 Transitive Matrix Based Applications The matrix representation of a PN shows the relationship between the structures of net and its behavior and linear algebraic techniques for the PN analysis depend on such matrix representation. The weighted place transitive matrix can efficiently be used to identify important structural aspects in the Petri net model of the control system. Moreover, the control flow is done on the basis of token flow in the PN models. The transitive matrix further provides the token flow relation from its columns to respective rows e.g. it can be said that the column relation is a sum of the sent tokens from the place and the row relation is a sum of the received token in place . Through introducing the m × m place transitive matrix, we can evaluate transition enabling firing, and calculate quantity and sequence of transition enabling firing. The method to construct the transitive matrix from directed graph of PN model and the basic definition of transitive matrix can be found in the work of Liu et al32. Transitive Matrix: Definition8: (Transitive matrix)32 Letbe place transitive matrix and let be transition transitive matrix with rows and columns, where = [N] .[N]and = [N] [N]. The labeled place transitive matrixVP is a matrix satisfying: VP = [N] diag t … t) ([N] , where the elements of VP describe the direct transferring relation from one place to another through one or more transitions. Definition9: (Weighted place transitive matrix)32 The Weighted place transitive matrix is denoted as VP which is a transformation from VP: if a transition appears times in the same column of VP, then replace in VP by /s in VP, otherwise the elements in VP are the same as VPDefinition 10: (Marking transformation)32,37The transformation of marking is defined as k+1 = M LVP, where k+1) is a -vector of nonnegative integer and is a marking calculated from reachable marking = p1(k), p), … p)], VP is the weighted place transitive matrix. The transformation equation shows the flow relation of a token in from ) to k+1) by the weighted place transitive matrix. In this equation, if the coefficient of in the function ij iVPpL  is an integer, then let 1 ijiVPpL =  , which means tokens in ) can be transferred from ) to k+1); otherwise, let 0 ijiVPpL = , which means tokens in ) can not be transferred from ) to k+1). However, k+1) only presents the flow relation of tokens, it may not necessary correspond to a reachable marking k+132. Example: The transitive matrix of a place/transition net given figure 1 is shown below. Now consider, p1(k), p, p), ), )] then k+1 = M LVP thus obtained is given as k+1[0, t1, (p+ p))/2, t3, t3. Further, | t | = 1 when fires, or | t | =0 when t doesn’t fire as well as |p| =1 when a place p has a token and zero otherwise. The reachable marking k+1shows the token flow from the marking ) as by firing the transition t1, the token of the place p1 would move to p2. Thereafter, t2 can only be fired when both p2 and p5 have tokens while the token of these places would move to p3. Similarly, the token of p3 can move to p4 and p5 at the same time in the reachable marking k+1), by firing of the transition t3. Figure-1 An example Petri net VP= 100 0001000 010 0000100 001 0000011 000010          = 33 2 0000 0000 000 00000 0000 tt tt t         , and the weighted place transitive matrix is, VP = 12 33 2 0000 00200 000 00000 00200 tt tt t         . P1 P2 P3 P4 P5 t1 t2 t3 Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 25 Application of Transitive Matrix based Techniques in the Petri Net Analysis: Structural properties have been examined using the equation of the transitive matrices and characteristic polynomial. Furthermore, behavioral properties concerning the transition firing orders have also been discussed using the power of the transitive matrices. A divide and conquer analysis method has been proposed by dividing the Petri nets into the subnets using transitive matrix under the condition of the safe Petri nets33. A decomposition method has been proposed for Petri net using the transitive matrix based on P-invariant in their several research articles34,35and timed PN slices have been applied to analyze the FMS model. The authors further defined the basic unit of concurrency (BUC) as a set of the executed control flows based on the behavioral properties in the net. The authors in their research divided original system into subsystem using the transitive matrix and permutated these sub-nets for analyzing the optimal cycle scheduling. As mentioned earlier that the transitive matrix may explain all relations between the place and transitions in PNs and one of the reasons for deadlock occurrence is the relationship between more than two transitions based on the conflict places. Therefore, several researchers used this feature of transitive matrix and addressed the deadlock problems using the transitive matrix36,37. Transition Vectors Based Applications In Section 2, the state-equation based on incidence matrix was defined as [N]. MM s =+  . However point to be noted for the state-equation is that the transition firing vector has to be put manually in the equation. In other words, the state-equation doesn’t provide any information about the enabling of a transition or a set of transitions at given marking. Therefore, there is a need to develop a method to calculate the enabled transition(s) at a given marking in order to simulate the PN mathematically. The Transition Vectors (TVs) can be used to determine all the enabled transitions at a given state of system and identify them whether they are concurrently enabled. Transition vectors (TVs) can be viewed as a powerful tool to describe the structure of PN models in a systematic and simplified manner. Further, TVs explain the relation between places and transitions of net in such a way that they provide not only the token flow relation but the complete information about the structure. Further, they can also recognize whether the enabled transitions are independent. In addition, TVs have the feature to detect the concurrently enabled transitions and to get the resultant marking after their execution. The transition vectors (TVs) are two vectors and with |P| components such that the vector is a |P|-vector whose ithcomponent corresponds to the output place and contains its input transition(s) and is a |P|-vector whose ith component corresponds to the input place and contains its output transition(s), 1,2,, iP "=  . Formal definition, procedure for construction and detailed discussion about the TVs can be found in the work of Ahmad et al.38, 9. Construction of TVs: Definition 11: (Transition Vectors) 10 a P -vector is a column vector :() Ii TPIp ® indexed by P and a P -vector is a column vector :() Oi TPOp ® indexed by P , where () i Ip and () i Op are the sets of input and output transitions, respectively. The definition implies that the vector I T is a P -vector whose ith component corresponds to the output place i p and contains its input transition(s) and O T is a P -vector whose ith component corresponds to the input place i p and contains its output transition(s), 1,2,, iP "=  . For example, the TVs for figure 1 are 51234 T I Tttttt =+ \n and12345 T O Tttttt =+ \n . The TVs in Figure 1 are indexed by places to refer the components of TVs and stand for output (input) places for transitions in the components of I T ( O T ). The representation of TVs in figure 2 is just to make them conceivable. Further, the coefficient of an arbitrary transition j t in I T is equal to the number of its input places, i.e., () j It while the coefficient an arbitrary transition j t in O T is equal to the number of its output places, i.e., () j Ot . Example: Let51234 T I Tttttt =+ \n , 12345 T O Tttttt =+ \n and [1000] T are TVs a marking for PN given in figure 1. To identify the enabling condition, the linear combination 12 kO MTtt =+ indicates that the number of entries of 1 t is one, i.e., 1 tM = and the coefficient of 1 t in I T is 1 tC = . The condition 11 /k tMt NC = is satisfied which communicates that 1 t is enabled at k M , similarly 2 t is also enabled due to 22 / tMt NC = . For marking transformation, if the enabled transition 1 t at k M is fired, since 11 () O tTp Î therefore 11 ()()1110 kkMpMp =-=-= and ()() kiki MpMp ¢ = for 2,3,4 i = . The transformed vector is [0000] T . Further, since 12 () I tTp Î , we replace ()1 Tp = and zero otherwise to get the vector [0100] k T . Finally, the transformed marking by firing 1 t , [0100] T is obtained by adding vectors k M ¢ and k I T . Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 26 Figure-2 An example of PN model and its TVs representationApplication of TVs in the Petri Net Analysis: Several structural aspects of important properties have been examined in 13 for the verification of PN models using simplified approach of TVs in order to overcome the shortcomings of existing methods of verification. The TVs have been used as a new method for deadlock detection and deadlock avoidance in a class of PNs called parallel process net with resources (PPNRs). The components of TVs of PPNRs identified the places representing the shared resources as well as the transitions to begin and finish the operations on these resources. In this way, the condition of operation flows has been determined from the components of to the components of through transitions in their components and used for deadlock detection. The authors further proposed the strategy of deadlock recovery in PPNRs by adding the control places. A method of analysis for PPNRs based on TVs has been presented in the literature10,38. The proposed analysis method is based on reduced reachability graph of PPNRs to verify the correspondence between required specification of manufacturing system and its PN representation. Moreover, relationship between the reduction of reachability graph and parallel structures in the PN model has also been discovered. Conclusion In this paper, different linear algebraic approaches for the analysis of PN based models have been discussed. Several analysis methods for the PN based systems discusses in this paper have been categorized into the structural invariants, transitive matrix based applications and transition vectors based applications. In this survey we tried to emphasize the merits and the demerits of these techniques. It has been established that the use of linear algebra based techniques for analysis and performance evaluation of PNs is a rich field that is known under the name of structural as well as behavioral analysis of PNs. In addition, from the review of the literature presented above following are the concluding remarks. Reduction of constraints and control places: The authors used linear constraints to specify forbidden states and the strategy was based on the equivalence between the set of forbidden states and the set of linear constraints obtained from it. Invariant based optimal controller synthesis by adding the control places has been presented in the literature. These sorts of techniques have the drawback that the number of forbidden states, and consequently, the number of constraints, are large and lead to a large number of control places. Several authors tackle this issue by taking the structural properties into account and adopted the reduction of constrains and used the linear programming, linear integer programming and mixed integer programming methods for solving the set of integer equations. References 1.Nikhil D., Rajesh A., Vijay M., Sandeep K., Mohit, Satyapal, Pardeep K., Thermodynamics and the Design, Analysis and Improvement of a Combined Heat and Power System, Res.J.Recent Sci., 1(3), 76-79 (2012)2.Ali B., Shahbazi S. and Vaezi S., Analysis of the Sampling in Quality Control Charts in non uniform Process by using a New Statistical Algorithm, Res. J. Recent Sci.,1(8), 36-41 (2012)5121324345 O ttttt TT ttttt \n \n\r\r\r\r == \r\r\r\r\r\r t1 p1 t4 t5 t3 p4 p2 t2 p3 Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 27 3.Fam D.F., Koh S.P., Tiong S.K. and Chong K.H., Qualitative Analysis of Stochastic Operations in Dual Axis Solar Tracking Environment, Res. J. Recent Sci.,1(9), 74-78 (2012)4.Krishan K. and Aggarwal M.L., A Finite Element Approach for Analysis of a Multi Leaf Spring using CAE Tools, Res. J. Recent Sci.,1(2), 92-96 (2012)5.Balamuralitharan S. and Rajasekaran S., Analysis of G-CSF Treatment of CN using Fast Fourier Transform, Res. J. Recent Sci.,1(4), 14-21 (2012)6.Hrúz B. and Zhou M.C., Modeling and Control of Discrete-event Dynamic Systems: Advanced Textbooks in Control and Signal Processing,Springer-VerlagLondon Limited (2007)7.Jiao L., Huang H. and To-yat Cheung, , Handling resource sharing problem using property-preserving place fusions of Petri nets, Journal of Circuits, Systems, and Computers17, 365-387 (2008)8.Ahmad F., Khan S.A., Specification and verification of safety properties along a crossing region in a railway network control, Applied Mathematical Modeling, In Press, DOI:10.1016/j.apm.2012.10.047 (2012)9.Ahmad F., Huang H. J., and Wang X. L., Petri net modeling and deadlock analysis of parallel manufacturing processes with shared resources, Journal of Systems and Software,83, 675-688 (2010)10.Ahmad F., Huang H., Wang X-L., Analysis of the Petri net model of parallel manufacturing processes with shared resources, Information Sciences,181, 5249–5266 (2011)11.Murata T., Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE20(4),(1989) 12.Desel J., Basic Linear Algebraic Techniques for Place/Transition Nets. In Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science, W. Reisig and G. Rozenberg (Eds.)1491, 257-308 (1998)13.Ahmad F., Huang H.J. and Wang X.L., Verification of Petri net models based on transition vectors, In Proc. IEEE Int. Conf. of ICMLC, 1542-1547 (2008)14.Best E., Structure Theory of Petri Nets: The Free Choice Hiatus, LNCS, Springer Verlag, 254, 168-205 (1987)15.Sifakis J., Structural Properties of Petri Nets, LNCS No. 64. Springer-Verlag, (1978) 16.Murata T., State equation, controllability, and maximal matchings for Petri nets, IEEE Trans. Automat. Contr. Ac-22(3), 412 - 416 (1977)17.Li Z.W. and Zhou M.C., Deadlock Resolution in Automated Manufacturing Systems: Advances in Industrial Control, Springer-Verlag London Limited (2009)18.Barkaoui K., Chaoui A. and Zouari B., Supervisory control of discrete event systems based on structure theory of Petri nets, Proc. IEEE Int Systems, Man, and Cybernetics Computational Cybernetics and Simulation, Conf, , 3750-3755 (1997) 19.Amer-Yahia C., Zerhouni N., El-Moudni A., Ferney M., State equation and stability of a class of continuous Petri nets. Application to manufacturing lines Proc. INRIA/IEEE Symp Emerging Technologies and Factory Automation ETFA '95, , 313-321 (1995)20.Demongodin I., Caradec M., Prunet F., Fundamental concepts of analysis in batches Petri nets, Proc. IEEE Int Systems, Man, and Cybernetics Conf, , 845-850 (1998)21.Zurawski R., Verifying correctness of interfaces of design models of manufacturing systems using functional abstractions, IEEE Transactions on Industrial Electronics, 44, 307-320 (1997)22.Ramachandran P., Kamath M., On place invariant sets and the rank of the incidence matrix of Petri nets, Proc. IEEE Int Systems, Man, and Cybernetics Conf, , 160-165 (1998)23.Miyazawa I., Kobayashi N., Sekiguchi T., The modeling and analyzing of sequential control systems using invariant properties of Petri net, Proc. IEEE IECON 22nd Int Industrial Electronics, Control, and Instrumentation Conf, , 451-456 (1996)24.Lu Y., Wei G., To-yat Cheung, A use case driven approach to synthesis and analysis of flexible manufacturing systems, Proc. IEEE Int Systems, Man, and Cybernetics Conf, , 2445-2450 (2001)25.Li L., Hadjicostis C.N. and Sreenivas R.S., Fault detection and identification in Petri net controllers, Proc. CDC Decision and Control 43rd IEEE Conf, , 5248-5253 (2004)26.Kezic D., Matic P. and Racic N., P-Invariant based Petri net traffic controller, Proc. 17th Mediterranean Conf. Control and Automation MED '09, 1096-1101 (2009)27.Ge J., Hu H. and Lu J., Invariant Analysis for the Task Refinement of Workflow Nets, Proc. Int Computational Intelligence for Modelling, Control and Automation and Int. Conf. Intelligent Agents, Web Technologies and Internet Commerce Conf (2006)28.Dideban A., and Alla H., From forbidden state to linear constraints for the optimal supervisory control, Control Engineering and Applied Informatics (CEAI), 7(3), 48–55 (2005)29.Dotoli M., Fanti M.P., Mangini A.M. and Ukovich W., On-line fault diagnosis in a Petri Net framework Proc. IEEE Int. Conf. Automation Science and Engineering CASE 2009, 42-47 (2009) 30.Chen Y., Li Z., Khalgui M. and Mosbahi O., Design of a Maximally Permissive Liveness- Enforcing Petri Net Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(5), 21-28, May (2013) Res. J. Recent Sci. International Science Congress Association 28 Supervisor for Flexible Manufacturing Systems, IEEE Transactions on Automation Science and Engineering, , 374-393 (2011)31.Chao D.Y., Enumeration of lost states of a suboptimal control model of a well-known S3PR, IET Control Theory and Applications, , 1277-1286 (2011)32.Liu J., Itoh Y., Miyazawa I., Seikiguchi T., A Research on Petri nets Properties using Transitive matrix, Proceeding IEEE SMC 99, 888-893 (1999) 33.Song Y.J. and Lee J.K., Analysis of Petri net models using transitive matrix, Proc. IEEE Int Systems, Man, and Cybernetics Conf, , 3122-3127 (2000) 34.Lee J-K., Korbaa O., Scheduling analysis of FMS: An unfolding timed Petri nets approach, Mathematics and Computers in Simulation, 70, 419-432(2006). 35.Lee J.K. and Korbaa O., Modeling and scheduling of ratio-driven FMS using unfolding time Petri nets, Computers and Industrial Engineering,46(4), 639-653 (2004) 36.Kim S., Lee S., Lee J., Deadlock Analysis of Petri Nets Based on the Resource Share Places Relationship, Proc. IMACS Multiconference Computational Engineering in Systems Applications, , 59-64 (2006)37.Li J., H.J. Huang F. Ahmad, Deadlock avoidance of a kind of JSP with multi-resources sharing, In Proc. IEEE 11th Joint Conference on Information Science, 8th International Conference on Computational Intelligence and Natural Computing, Atlantis Press (2008)38.Ahmad F., Petri net Analysis based on Transition Vectors, PhD Thesis of Harbin Institute of Technology, China (2009)