Limits of Modularity

Article type: Research Article

Authors: Bednarczyk, Marek A.

Affiliations: Institute of Computer Science, Polish Academy of Sciences Gdańsk, Poland. E-mail: m.bednarczyk@ipipan.gda.pl

Abstract: 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.

Keywords: Theory of computation, software/hardware design and implementation, concurrency, partially commutative free monoids, Mazurkiewicz traces, code problem

Journal: Fundamenta Informaticae, vol. 74, no. 2-3, pp. 167-187, 2006