Navegar

Colección

Datos Estadísticas

Artículo

Abstract:

We introduce the notion of a T-path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between T-paths and firable sequences of transitions. Let us consider a Petri net P=〈P,T,A,M0〉 and the set of places with a positive marking in M0, i.e., P0=p|M0(p)>0. If we regard the net as a directed graph, the existence of a simple path from any place in P0 to a transition t is, of course, a necessary condition for the potential firability of t. This is sufficient only if the net is a state machine, where |•t|=|t•|=1 for all t∈T. In this paper we show that the existence of a T-path from any subset of P0 to a transition t is a more restrictive condition and is, again, a necessary condition for the potential firability of t. But, in this case: (a) if P is a conflict-free Petri net, this is also a sufficient condition, (b) if P is a general Petri net, t is potentially firable by increasing the number of tokens in P0. For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of coverable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i.e., O(|P|+|T|+|A|), for a net P=〈P,T,A,M0〉. Previous results for this class of networks are given by Howell et al. (1987) [20], providing algorithms for solving problems in conflict-free nets in O(|P|×|T|) time and space. Given a Petri net and a marking M, the well-known coverability problem consists in finding a reachable marking M′ such that M′

Registro:

Documento: Artículo
Título:Linear time analysis of properties of conflict-free and general Petri nets
Autor:Alimonti, P.; Feuerstein, E.; Laura, L.; Nanni, U.
Filiación:Dipartimento di Informatica e Sistemistica Antonio Ruberti, Sapienza Universitéy of Rome, via Ariosto 25, I-00185 Roma, Italy
Departamento de Computacion, Universidad de Buenos Aires, Pabellon I, Ciudad Universitéaria, 1428 Buenos Aires, Argentina
Palabras clave:Boundedness; Conflict-free Petri nets; Coverability; Directed hypergraphs; Incremental algorithms; Liveness; Marked graphs; Petri nets; Boundedness; Conflict free; Coverability; Directed hypergraphs; Incremental algorithm; Liveness; Marked graphs; Algorithms; Graph theory; Petri nets; Teaching; Problem solving
Año:2011
Volumen:412
Número:4-5
Página de inicio:320
Página de fin:338
DOI: http://dx.doi.org/10.1016/j.tcs.2010.09.030
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v412_n4-5_p320_Alimonti.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v412_n4-5_p320_Alimonti

Referencias:

  • Aho, A.V., Hopcroft, J.E., Ullman, J.D., (1974) The Design and Analysis of Computer Algorithms, , Addison-Wesley
  • Ausiello, G., D'Atri, A., Sacc, D., Graph algorithms for functional dependency manipulation (1983) Journal of the ACM, 30, pp. 752-766
  • Ausiello, G., Franciosa, P.G., Frigioni, D., Partially dynamic maintenance of minimum weight hyperpaths (2005) Journal of Discrete Algorithms, 3 (1), pp. 27-46
  • Ausiello, G., Italiano, G.F., Online algorithms for polynomially solvable satisfiability problems (1991) Journal of Logic Programming, 10, pp. 69-90
  • Ausiello, G., Italiano, G.F., Nanni, U., Dynamic maintenance of directed hypergraphs (1990) Theoretical Computer Science, 72 (23), pp. 97-117
  • Berge, C., (1973) Graphs and Hypergraphs, , North Holland Amsterdam
  • Best, E., A note on persistent Petri nets (2008) Lecture Notes in Computer Science, 5065, pp. 427-438. , Springer-Verlag
  • Boley, H., Directed recursive labelnode hypergraphs: A new representation language (1977) Artificial Intelligence, 9, pp. 49-85
  • Cheng, A., Esparza, J., Palsberg, J., Complexity results for 1-safe nets (1995) Theoretical Computer Science, 147 (12), pp. 117-136
  • Chu, F., Xie, X., Deadlock analysis of Petri nets using siphons and mathematical programming (1997) IEEE Transactions on Robotics and Automation, 13 (6), pp. 793-804
  • Commoner, F., Holt, A.W., Even, S., Pnueli, A., Marked directed graphs (1971) Journal of Computer and System Sciences, 5 (5), pp. 511-523
  • Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., (2001) Introduction to Algorithms, , second ed. MIT Press
  • Crespi-Reghizzi, S., Mandrioli, D., A decidability theorem for a class of vector additions systems (1975) Information Processing Letters, 3 (3), pp. 78-80
  • Esparza, J., Nielsen, M., Decidability issues for Petri nets a survey (1994) Bulletin EATCS, 52, pp. 245-262
  • Esparza, J., Silva, M., A polynomial-time algorithm to decide liveness of bounded free-choice nets (1992) Theoretical Computer Science, 102 (1), pp. 185-205
  • Gallo, G., Longo, G., Nguyen, S., Pallottino, S., Directed Hypergraphs and Applications (1990) Technical Report 3/90, , Dip. di Informatica, Univ. of Pisa, Italy, January
  • Ghezzi, C., Mandrioli, D., Morasca, S., Pezz, M., A unified high-level Petri net formalism for time-critical systems (1991) IEEE Transactions on Software Engineering, 17 (2), pp. 160-172
  • Hack, M.H.T., The recursive equivalence of the reachability problem and the liveness problem for Petri nets and vector addition systems (1974) 15th Annual Symposium on Switching and Automata Theory, pp. 156-164
  • Howell, R., Rosier, L., Problems concerning fairness and temporal logic for conflict-free Petri nets (1989) Theoretical Computer Science, 64 (3), pp. 305-329
  • Howell, R., Rosier, L., Yen, H., An O(n1.5) algorithm to decide boundedness for conflict-free vector replacement system (1987) Information Processing Letters, 25 (1), pp. 27-33
  • Howell, R., Rosier, L., Yen, H., A taxonomy of fairness and temporal logic problems for Petri nets (1991) Theoretical Computer Science, 82 (2), pp. 341-372
  • Jeng, M.D., Xie, X., Analysis of modularly composed nets by siphons (1999) IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 29 (4), pp. 399-406
  • Jones, N.D., Landweber, L.H., Lien, Y.E., Complexity of some problem in Petri nets (1977) Theoretical Computer Science, 4 (3), pp. 277-299
  • Karp, R.M., Miller, R., Parallel program schemata (1969) Journal of Computer and System Sciences, 3 (2), pp. 147-195
  • Keller, R., A fundamental theorem of asynchronous parallel computation (1975) Lecture Notes in Computer Science, 24, pp. 102-112
  • Landweber, L., Robertson, E., Properties of conflict-free and persistent Petri nets (1978) Journal of the ACM, 25 (3), pp. 352-364
  • Lipton, R., The reachability problem requires exponential space (1976) Technical Report 62, , Department of Computer Science, Yale Universitéy
  • Mayr, E., An algorithm for the general Petri net reachability problem (1984) SIAM Journal on Computing, 13 (3), pp. 441-459
  • Murata, T., Petri nets: Properties, analysis and applications (1989) Proceedings of the IEEE, pp. 541-580
  • Peterson, J.L., Petri nets (1977) Computing Surveys, 9 (3), pp. 223-252
  • Petri, C.A., (1966) Communication with Automata, Technical Report Supplement 1 to Tech. Report RADC-TR-65-377, , Rome Air Development Center (US Air Force), 1962. Original in German: Kommunikation mit Automaten, Ph.D. Thesis, Univ. of Bonn, 1962
  • Piroddi, L., Cordone, R., Fumagalli, I., Combined siphon and marking generation for deadlock prevention in Petri nets (2009) IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 39 (3), pp. 650-661
  • Rackoff, C., The covering and boundedness problems for vector addition systems (1978) Theoretical Computer Science, 6 (2), pp. 223-231
  • Reisig, W., Petri Nets, An Introduction (1985) ETACS Monographs Theoretical Computer Science, , Springer-Verlag
  • Roditty, L., Zwick, U., A fully dynamic reachability algorithm for directed graphs with an almost linear update time (2004) STOC'04: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pp. 184-191. , Chicago, IL, June 1315, 2004 ACM
  • Tarjan, R.E., Efficiency of a good but not linear set union algorithm (1975) Journal of the ACM, 22 (2), pp. 215-225
  • Thakur, M., Tripathi, R., Linear connectivity problems in directed hypergraphs (2009) Theoretical Computer Science, 410, pp. 2592-2618
  • Yen, H., A unified approach for deciding the existence of certain Petri nets paths (1992) Information and Computation, 96 (1), pp. 119-137
  • Zhou, M.C., Dicesare, F., Parallel and sequential mutual exclusions for Petri net modeling for manufacturing systems with shared resources (1991) IEEE Transactions on Robotics and Automation, 7 (4), pp. 515-527

Citas:

---------- APA ----------
Alimonti, P., Feuerstein, E., Laura, L. & Nanni, U. (2011) . Linear time analysis of properties of conflict-free and general Petri nets. Theoretical Computer Science, 412(4-5), 320-338.
http://dx.doi.org/10.1016/j.tcs.2010.09.030
---------- CHICAGO ----------
Alimonti, P., Feuerstein, E., Laura, L., Nanni, U. "Linear time analysis of properties of conflict-free and general Petri nets" . Theoretical Computer Science 412, no. 4-5 (2011) : 320-338.
http://dx.doi.org/10.1016/j.tcs.2010.09.030
---------- MLA ----------
Alimonti, P., Feuerstein, E., Laura, L., Nanni, U. "Linear time analysis of properties of conflict-free and general Petri nets" . Theoretical Computer Science, vol. 412, no. 4-5, 2011, pp. 320-338.
http://dx.doi.org/10.1016/j.tcs.2010.09.030
---------- VANCOUVER ----------
Alimonti, P., Feuerstein, E., Laura, L., Nanni, U. Linear time analysis of properties of conflict-free and general Petri nets. Theor Comput Sci. 2011;412(4-5):320-338.
http://dx.doi.org/10.1016/j.tcs.2010.09.030