Navegar

Colección

Datos Estadísticas

Artículo

Bruni, R.; Melgratti, H.; Montanaric, U.; Sobociński, P.L. "Connector algebras for C/E and P/T nets' interactions" (2013) Logical Methods in Computer Science. 9(3)
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A quite flourishing research thread in the recent literature on componentbased systems is concerned with the algebraic properties of different classes of connectors. In a recent paper, an algebra of stateless connectors was presented that consists of five kinds of basic connectors, namely symmetry, synchronization, mutual exclusion, hiding and inaction, plus their duals, and it was shown how they can be freely composed in series and in parallel to model sophisticated \\glues". In this paper we explore the expressiveness of stateful connectors obtained by adding one-place buffers or unbounded buffers to the stateless connectors. The main results are: i) we show how different classes of connectors exactly correspond to suitable classes of Petri nets equipped with compositional interfaces, called nets with boundaries; ii) we show that the difference between strong and weak semantics in stateful connectors is reflected in the semantics of nets with boundaries by moving from the classic step semantics (strong case) to a novel banking semantics (weak case), where a step can be executed by taking some \\debit" tokens to be given back during the same step; iii) we show that the corresponding bisimilarities are congruences (w.r.t. composition of connectors in series and in parallel); iv) we show that suitable monoidality laws, like those arising when representing stateful connectors in the tile model, can nicely capture concurrency (in the sense of step semantics) aspects; and v) as a side result, we provide a basic algebra, with a finite set of symbols, out of which we can compose all P/T nets with boundaries, fulfilling a long standing quest. © R. Bruni, H. Melgratti, U. Montanari, and P. Sobociński.

Registro:

Documento: Artículo
Título:Connector algebras for C/E and P/T nets' interactions
Autor:Bruni, R.; Melgratti, H.; Montanaric, U.; Sobociński, P.L.
Filiación:Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo 3, I-56127 Pisa, Italy
Departamento de Computación, FCEyN, Universidad de Buenos Aires - CONICET, Pabellón I, Ciudad Universitaria, (C1428EGA) Buenos Aires, Argentina
ECS, University of Southampton, SO17 1BJ, United Kingdom
Palabras clave:C/E nets with boundaries; Connector algebras; P/T nets with boundaries; Tiles; Algebraic properties; Basic algebra; Component based systems; Compositional interfaces; Different class; Mutual exclusions; P/T net; Stateless connectors; Model checking; Petri nets; Semantics; Tile; Algebra
Año:2013
Volumen:9
Número:3
DOI: http://dx.doi.org/10.2168/LMCS-9(3:16)2013
Título revista:Logical Methods in Computer Science
Título revista abreviado:Log. Methods Comp. Sci.
ISSN:18605974
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18605974_v9_n3_p_Bruni

Referencias:

  • Arbab, F., Reo: A channel-based coordination model for component composition (2004) Math. Struct. in Comp. Science, 14 (3), pp. 329-366
  • Arbab, F., Bruni, R., Clarke, D., Lanese, I., Montanari, U., Tiles for Reo (2009) WADT 2008, volume 5486 of Lect. Notes in Comput. Sci, pp. 37-55. , Springer, In A. Corradini and U. Montanari, editors
  • Arbab, F., Rutten, J., A coinductive calculus of component connectors (2002) WADT 2002, volume 2755 of Lect. Notes in Comput. Sci, pp. 34-55. , Springer, In M. Wirsing, D. Pattinson, and R. Hennicker, editors
  • Baier, C., Sirjani, M., Arbab, F., Rutten, J., Modeling component connectors in Reo by constraint automata (2006) Sci. Comput. Program., 61 (2), pp. 75-113
  • Baldan, P., Corradini, A., Ehrig, H., Heckel, R., Compositional semantics for open Petri nets based on deterministic processe (2005) Math. Struct. in Comp. Science, 15 (1), pp. 1-35
  • Barbosa, M.A., Barbosa, L.S., Specifying software connectors (2004) ICTAC 2004, volume 3407 of Lect. Notes in Comput. Sci, pp. 52-67. , Springer, In Z. Liu and K. Araki, editors
  • Basu, A., Bozga, M., Sifakis, J., Modeling heterogeneous real-time components in BIP (2006) SEFM 2006, pp. 3-12. , IEEE Computer Society
  • Bernardinello, L., Monticelli, E., Pomello, L., On preserving structural and behavioural properties by composing net systems on interfaces (2007) Fundam. Inform., 80 (1-3), pp. 31-47
  • Best, E., Devillers, R.R., Koutny, M., The Box algebra = Petri nets + process expressions (2002) Inf. Comput., 178 (1), pp. 44-100
  • Best, E., Koutny, M., Process algebra: A Petri-net-oriented tutorial (2003) Lectures on Concurrency and Petri Nets, volume 3098 of Lect. Notes in Comput. Sci, pp. 180-209. , Springer, In J. Desel, W. Reisig, and G. Rozenberg, editors
  • Bliudze, S., Sifakis, J., The algebra of connectors structuring interaction in BIP (2008) IEEE Trans. Computers, 57 (10), pp. 1315-1330
  • Bruni, R., (1999) Tile Logic for Synchronized Rewriting of Concurrent Systems, , PhD thesis, Computer Science Department, University of Pisa
  • Bruni, R., Gadducci, F., Montanari, U., Normal forms for algebras of connection (2002) Theoret. Comput. Sci., 286 (2), pp. 247-292
  • Bruni, R., Lanese, I., Montanari, U., A basic algebra of stateless connectors (2006) Theoret. Comput. Sci., 366 (1-2), pp. 98-120
  • Bruni, R., Melgratti, H.C., Montanari, U., A connector algebra for P/T nets interactions (2011) CONCUR 2011, volume 6901 of Lect. Notes in Comput. Sci, pp. 312-326. , Springer, In J.-P. Katoen and B. König, editors
  • Bruni, R., Melgratti, H.C., Montanari, U., Connector algebras, petri nets, and bip (2012) PSI 2011, Ershov Memorial Conference, volume 7162 of Lect. Notes in Comput. Sci, pp. 19-38. , Springer, In E. M. Clarke, I. Virbitskaite, and A. Voronkov, editors
  • Bruni, R., Montanari, U., Dynamic connectors for concurrency (2002) Theoret. Comput. Sci., 281 (1-2), pp. 131-176
  • Buscemi, M.G., Sassone, V., High-level Petri nets as type theories in the Join calculus (2001) FoSSaCS 2001, volume 2030 of Lect. Notes in Comput. Sci, pp. 104-120. , Springer, In F. Honsell and M. Miculan, editors
  • Clarke, D., Costa, D., Arbab, F., Connector colouring I: Synchronisation and context dependency (2007) Sci. Comput. Program., 66 (3), pp. 205-225
  • Corradini, A., Montanari, U., An algebraic semantics for structured transition systems and its application to logic programs (1992) Theoret. Comput. Sci., 103, pp. 51-106
  • Devillers, R., The semantics of capacities in P/T nets (1988) European Workshop on Applications and Theory in Petri Nets, volume 424 of Lect. Notes in Comput. Sci, pp. 128-150. , Springer, In G. Rozenberg, editor
  • Devillers, R., Klaudel, H., Koutny, M., Pommereau, F., Asynchronous box calculus (2003) Fundam. Inform., 54 (4), pp. 295-344
  • Dickson, L.E., Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors (1913) Amer. Journal Math., 35 (4), pp. 413-422
  • Fabre, E., On the construction of pullbacks for safe petri nets (2006) ICATPN 2006, volume 4024 of Lect. Notes in Comput. Sci, pp. 166-180. , Springer, In S. Donatelli and P. S. Thiagarajan, editors
  • Ferrari, G.L., Montanari, U., Tile formats for located and mobile systems (2000) Inf. Comput., 156 (1-2), pp. 173-235
  • Fiadeiro, J.L., Maibaum, T., Categorical semantics of parallel program design (1997) Sci. Comput. Program., 28 (2-3), pp. 111-138
  • Gadducci, F., Montanari, U., The tile model (2000) Proof, Language, and Interaction, pp. 133-166. , The MIT Press
  • Johnson, M., Algebraic Methodology and Software Technology (1997) 6th International Conference, AMAST'97, , editor, Sydney, Australia, December 13-17, 1997, Proceedings, volume 1349 of Lect. Notes in Comput. Sci. Springer
  • Jongmans, S.-S.T.Q., Arbab, F., Correlating formal semantic models of Reo connectors: Connector coloring and constraint automata (2011) ICE 2011, volume 59 of Elect. Proc. in Th. Comput. Sci, pp. 84-103. , In A. Silva, S. Bliudze, R. Bruni, and M. Carbone, editors
  • Katis, P., Sabadini, N., Walters, R.F.C., Representing Place/Transition nets in Span(Graph), pp. 322-336. , In Johnson [28]
  • Katis, P., Sabadini, N., Walters, R.F.C., Span(Graph): A categorial algebra of transition systems, pp. 307-321. , In Johnson [28]
  • Kleijn, J., Koutny, M., Causality in structured occurrence nets (2011) Dependable and Historic Computing, volume 6875 of Lect. Notes in Comput. Sci, pp. 283-297. , Springer, In C. B. Jones and J. L. Lloyd, editors
  • Kleijn, J., Koutny, M., Localities in systems with a/sync communication (2012) Theoret. Comput. Sci., 429 (0), pp. 185-192
  • Kleijn, J., Koutny, M., Pietkiewicz-Koutny, M., Regions of petri nets with a/sync connections (2012) Theoret. Comput. Sci., 454 (0), pp. 189-198
  • Koutny, M., Best, E., Operational and denotational semantics for the Box algebra (1999) Theoret. Comput. Sci., 211 (1-2), pp. 1-83
  • Koutny, M., Esparza, J., Best, E., Operational semantics for the Petri Box calculus (1994) CONCUR'94, volume 836 of Lect. Notes in Comput. Sci, pp. 210-225. , Springer, In B. Jonsson and J. Parrow, editors
  • Larsen, K.G., Xinxin, L., Compositionality through an operational semantics of contexts (1990) ICALP'90, volume 443 of Lect. Notes in Comput. Sci, pp. 526-539. , Springer, In M. Paterson, editor
  • Leifer, J.J., Milner, R., Transition systems, link graphs and Petri nets (2006) Math. Struct. in Comput. Sci., 16 (6), pp. 989-1047
  • Meseguer, J., Conditional rewriting logic as a unified model of concurrency (1992) Theoret. Comput. Sci., 96, pp. 73-155
  • Montanari, U., Rossi, F., Graph rewriting, constraint solving and tiles for coordinating distributed systems (1999) Applied Categorical Structures, 7 (4), pp. 333-370
  • Nielsen, M., Priese, L., Sassone, V., Characterizing behavioural congruences for Petri nets (1995) CONCUR'95, volume 962 of Lect. Notes in Comput. Sci, pp. 175-189. , Springer, In I. Lee and S. A. Smolka, editors
  • Perry, D.E., Wolf, E.L., Foundations for the study of software architecture (1992) ACM SIGSOFT Software Engineering Notes, 17, pp. 40-52
  • Plotkin, G.D., A structural approach to operational semantics (2004) J. Log. Algebr. Program, 60-61, pp. 17-139
  • Priese, L., Wimmel, H., A uniform approach to true-concurrency and interleaving semantics for Petri nets (1998) Theoret. Comput. Sci., 206 (1-2), pp. 219-256
  • Reisig, W., (1985) Petri Nets: An Introduction, volume 4 of Monographs in Theoretical Computer Science, , An EATCS Series. Springer
  • Sassone, V., Sobociński, P., A congruence for Petri nets (2005) Electr. Notes in Theor. Comput. Sci., 127 (2), pp. 107-120
  • Selinger, P., A survey of graphical languages for monoidal categories (2011) New structures for physics, pp. 289-355
  • Sobociński, P., A non-interleaving process calculus for multi-party synchronisation (2009) ICE 2009, volume 12 of Elect. Proc. in Th. Comput. Sci, pp. 87-98. , In F. Bonchi, D. Grohmann, P. Spoletini, and E. Tuosto, editors
  • Sobociński, P., Representations of Petri net interactions (2010) CONCUR 2010, volume 6269 of Lect. Notes in Comput. Sci, pp. 554-568. , Springer, In P. Gastin and F. Laroussinie, editors
  • Sobociński, P., Relational presheaves as labelled transition systems (2012) CMCS 2012, volume 7399 of Lect. Notes in Comput. Sci, pp. 40-50. , Springer, In D. Pattinson and L. Schröder, editors
  • Stefanescu, G., Reaction and control I. Mixing additive and multiplicative network algebras (1998) Logic Journal of the IGPL, 6 (2), pp. 348-369

Citas:

---------- APA ----------
Bruni, R., Melgratti, H., Montanaric, U. & Sobociński, P.L. (2013) . Connector algebras for C/E and P/T nets' interactions. Logical Methods in Computer Science, 9(3).
http://dx.doi.org/10.2168/LMCS-9(3:16)2013
---------- CHICAGO ----------
Bruni, R., Melgratti, H., Montanaric, U., Sobociński, P.L. "Connector algebras for C/E and P/T nets' interactions" . Logical Methods in Computer Science 9, no. 3 (2013).
http://dx.doi.org/10.2168/LMCS-9(3:16)2013
---------- MLA ----------
Bruni, R., Melgratti, H., Montanaric, U., Sobociński, P.L. "Connector algebras for C/E and P/T nets' interactions" . Logical Methods in Computer Science, vol. 9, no. 3, 2013.
http://dx.doi.org/10.2168/LMCS-9(3:16)2013
---------- VANCOUVER ----------
Bruni, R., Melgratti, H., Montanaric, U., Sobociński, P.L. Connector algebras for C/E and P/T nets' interactions. Log. Methods Comp. Sci. 2013;9(3).
http://dx.doi.org/10.2168/LMCS-9(3:16)2013