Limits of Modularity

• Autorzy: Bednarczyk M.A.
• Języki publikacji: EN

Abstrakty

EN

It has been observed that various synchronisation operators underlying the modular design of concurrent systems can be explained as pullbacks in suitable categories of concurrent systems. Here, the boundaries of such approach are investigated. For this purpose we study the issue of completeness in categories of trace monoids. It turns out that (finite) completeness is achieved if trace monoids with concurrency preserving homomorphisms are considered. Taking arbitrary monoid homomorphisms leads, in general, to incompleteness. The results obtained are used to reveal an area in which the code problem for trace monoids, undecidable in general, has always a positive answer.

Słowa kluczowe

EN

theory of computation; software/hardware design and implementation; concurrency; partially commutative free monoids; Mazurkiewicz traces; code problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 2,3
• Strony: 167--187
• Opis fizyczny: bibliogr. 30 poz.

Twórcy

autor

Bednarczyk M.A.

• Institute of Computer Science, Polish Academy of Science, Gdańsk, Poland,

Bibliografia

• [1] A. Arnold, Finite transition systems. Prentice-Hall, (1992).
• [2] E. Badouel, M. A. Bednarczyk and Ph. Darondeau, Generalized automata and their net representation, in H. Ehrig et al. eds., Unifying Petri Nets, Advances in Petri Nets, LNCS 2128 (Springer, Berlin, 2001) 304-345.
• [3] E. Badouel and P. Darondeau, Dualities between Nets and Automata Induced by Schizophrenic Objects. Proc. Sixth Int. Conf. on CTCS, LNCS 953 (Springer, Berlin, 1995) 24-43
• [4] M. A. Bednarczyk, Categories of asynchronous systems. PhD Thesis 1-88, (University of Sussex, 1988).
• [5] M. A. Bednarczyk, L. Bernardinello, B. Caillaud, W. Pawowski and L. Pomello, Modular system development with pullbacks, in W. van der Aalst and E. Best, eds., Proc. ICATPN 2003, LNCS 2679 (Springer, Berlin, 2003) 140-160.
• [6] M. A. Bednarczyk and A. M. Borzyszkowski, General morphisms of Petri nets In: J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), Automata, Languages and Programming, Proc. 26th ICALP'99, LNCS 1644 (Springer, Berlin, 1999) 190-199.
• [7] M. A. Bednarczyk and A. M. Borzyszkowski, On concurrent realizations of reactive systems and their morphisms, in H. Ehrig et al. eds., Unifying Petri Nets, Advances in Petri Nets, LNCS 2128 (Springer, Berlin, 2001) 346-379.
• [8] M. A. Bednarczyk, A.M. Borzyszkowski andW. Pawowski, General congruences-Epimorphisms in CAT. Theory and Applications of Categories 5(11) (1999) 266-280.
• [9] M. A. Bednarczyk, A. M. Borzyszkowski and R. Somla, Finite completeness of categories of Petri nets. Fundamenta Informaticae, 43(1-4) (2000) 21-48.
• [10] L. Bernardinello, C. Ferigato and L. Pomello, Towards modular synthesis of EN systems, in B. Caillaud et al. eds. Synthesis and Control of Discrete Event Systems, (Kluwer, 2002) 103-113.
• [11] M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets, Fundamenta Informaticæ, X (1987) 323-336.
• [12] F. de Cindio, G. de Michelis, L. Pomello and C. Simone, Superposed automata nets, in C. Girault and W. Reisig, eds., Informatik-Fachberichte 52: Application and Theory of Petri Nets: Selected Papers from the First and Second EuropeanWorkshop on Application and Theory of Petri Nets, Strasbourg, Sep. 23-26, 1980, Bad Honnef, Sep. 28-30, 1981, (Springer-Verlag, 1982) 269-279.
• [13] R. Cori and D. Perrin, Automates et commutations partielles, R.A.I.R.O.-Informatique Théoretique et Applications, 19 (1985) 21-32.
• [14] V. Diekert, Combinatorics on traces, LNCS 454 (Springer, Berlin, 1990).
• [15] V. Diekert, A. Muscholl and K. Reinhardt, On codings of traces, in E. W. Mayr and C. Peuch, eds., Proc. STACS'95, LNCS 900 (Springer, Berlin, 1995) 385-396.
• [16] V. Diekert and G. Rozenberg, eds., The Book of Traces, (World Scientific, Singapore, 1995).
• [17] C. Duboc, Commutations dans les monoides libres: un cadre théoretique pour l'étude du parallelisme, These, Faculté des Sciences de l'Université de Rouen, (1986).
• [18] A. Ehrenfeucht and G. Rozenberg, Partial (set) 2 structures, I & II. Acta Informatica, 27(4) (1990) 315-368.
• [19] S. MacLane, Categories for the Working Mathematician. Graduate Texts in Mathematics (Springer, Berlin, 1971).
• [20] A. Mazurkiewicz, Concurrent program schemes and their interpretations. Technical Report DAIMI Rep. PB-78, Aarhus University, 1977.
• [21] A. Mazurkiewicz, Introduction to trace theory. In [16], (World Scientific, Singapore, 1995) 3-41.
• [22] R. Morin, Decompositions of asynchronous systems, in Proc. CONCUR'98, LNCS 1466 (Springer, Berlin, 1998) 549-564.
• [23] A. Muscholl, Decision and complexity issues on concurrent systems. Habilitation Thesis (Stuttgart, 1999).
• [24] M. Nielsen, G. Plotkin and G. Winskel, Petri nets, event structures and domains. Theoretical Computer Science 13 (1981) 85-108.
• [25] L. Pomello and L. Bernardinello, Formal tools for modular system development, in Jordi Cortadella and Wolfgang Reisig, eds., Proc. ICATPN 2004, LNCS 3099 (Springer, Berlin, 2004) 77-96.
• [26] W. Reisig, Petri Nets, volume 4 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1985.
• [27] G.Winskel, Category theory and models of parallel computation, in D. Pitt et al,, eds., Category Theory and Computer Programming, LNCS 240 (Springer, Berlin, 1985) 266-281.
• [28] G. Winskel, Synchronisation trees, Theoretical Computer Science, 34 (1985) 33-82.
• [29] G. Winskel and M. Nielsen, Models for concurrency, chapter in Handbook of Logic Theoretical Computer Science IV, (1995).
• [30] W. Zielonka, Notes on finite asynchronous automata, RAIRO, Informatique Théoretique et Applications, 21 (1987) 99-135.