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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.