Limits of Modularity

• Autorzy: Bednarczyk M.

Warianty tytułu

PL

Granice modularności

• Języki publikacji: EN

Abstrakty

EN

It has been observed that various synchronisation operators that underly modular design of concurrent systems can be explained as {\em 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. In terms of code problem for trace monoids.

PL

Wcześnie zauważono, że modularne techniki konstruowania systemów współbieżnych oparte o mechanizmy synchronizacji można opisać jako (zmodyfikowane) produkty lub wręcz jako produkty włókniste w stosownych kategoriach systemów współbieżnych. Celem niniejszej pracy jest wyznaczenie granic stosowalności tego teorio-kategoryjnego podejścia. W tym celu w pracy rozważa się problem (skończonej) zupełności kategorii monoidów śladów Mazurkiewicza dla różnych klas morfizmów formalizującej pojęcie symulacji systemów. Okazuje się, że skończoną zupełność gwarantuje przyjęcie, iż obiektem badań są reprezentacje monoidów śladów postaci alfabet i relacja niezależności, zaś morfizmy to funkcje z alfabetu do monoidu śladów zachowujące niezależność. Z kolei akceptacja dowolnych homomorfizmów, niekoniecznie zachowujących niezależność, prowadzi na ogół do braku zupełności kategorii. Osiągnięte wyniki rozszerzają też obszar, w którym problem kodu dla monoidów śladów jest rozstrzygalny w sposób pozytywny.

Słowa kluczowe

EN

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

PL

teoria obliczeń; tworzenie i implementowanie systemów; współbieżność; częściowo przemienne monoidy wolne; ślady Mazurkiewicza; problem kodu

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2006
• Tom: Nr 989
• Strony: 1--21
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Bednarczyk M.

• Instytut Podstaw Informatyki PAN filia Gdańsk ul. Abrahama 18 81-825 Sopot,

Bibliografia

• [1] 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.
• [2] M. A. Bednarczyk, Categories of asynchronous systems. PhD Thesis 1-88, (University of Sussex, 1988).
• [3] 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.
• [4] 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.
• [5] M. A. Bednarczyk, A. M. Borzyszkowski and W. Pawłowski, General congruences — Epimorphisms in CAT. Theory and Applications of Categories 5(11) (1999) 266-280.
• [6] M. A. Bednarczyk, A. M. Borzyszkowski and R. Somla, Finite completeness of categories of Petri nets. Fundamenta Informaticae, 43(1-4) (2000) 21-48.
• [7] M. A. Bednarczyk, L. Bernardinello, B. Caillaud, W. Pawłowski 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.
• [8] 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.
• [9] M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets, Fundamenta Informaticse, X (1987) 323-336.
• [10] R. Cori and D. Perrin, Automates et commutations partieles, R.A.I.R.O.—Informatique Theoretique et Applications, 19 (1985) 21-32.
• [11] 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.
• [12] V. Diekert and G. Rozenberg, eds., The Book of Tinces, (World Scientific, Singapore, 1995).
• [13] C. Duboc, Commutations dans les monoides libres: un cadre theoretique pour l'etude du parallelisme, These, Faculte des Sciences de l'Universitć de Rouen, (1986).
• [14] A. Ehrenfeucht and G. Rozenberg, Partial (set) 2 structures, I & II. Acta Informatica, 27(4) (1990) 315-368.
• [15] S. MacLane, Categories for the Working Mathematician. Graduate Texts in Mathematics (Springer, Berlin, 1971).
• [16] R. Morin, Decompositions of asynchronous systems, in Proc. CON-CUR'98, LNCS 1466 (Springer, Berlin, 1998) 549-564.
• [17] A. Muscholl, Decision and complexity issues on concurrent systems. Habilitation Thesis (Stuttgart, 1999).
• [18] M. Nielsen, G. Plotkin and G. Winskel, Petri nets, event structures and domains. Theoretical Computer Science 13 (1981) 85-108.
• [19] W. Reisig, Petri Nets, volume 4 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1985.
• [20] 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.
• [21] G. Winskel, Synchronisation trees, Theoretical Computer Science, 34 (1985) 33-82.
• [22] G. Winskel and M. Nielsen, Models for concurrency, chapter in Handbook of Logic Theoretical Computer Science IV, (1995).
• [23] W. Zielonka, Notes on finite asynchronous automata, RAIRO, Informatique Theoretigue et Applications, 21 (1987) 99-135.