Finite labelling problem in event structures Export

@article{citeulike:3582107, abstract = {In event structures, one of the classical models of parallelism, the concept of nice labelling occurs: this consists in attributing label to each event of the structure, in such a way that two different events may have the same label if either they are in temporal causality or they are not the initial occurrences of incompatible actions. The problem is to minimize the number of labels. In this paper we are concerned with event structures admitting a finite nice labelling. We characterize those admitting a 2-labelling. Then we prove that for finite event structures the optimization of the labelling is an NP-hard problem. Finally, using combinatorial and order-theoretic tools, we investigate some special cases.}, author = {Assous, M.}, citeulike-article-id = {3582107}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0304-3975(94)90065-5}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/0304-3975(94)90065-5}, day = {17}, doi = {10.1016/0304-3975(94)90065-5}, issn = {03043975}, journal = {Theoretical Computer Science}, keywords = {causality, concurrency, eventstructure}, month = {January}, number = {1}, pages = {9--19}, posted-at = {2008-11-20 11:31:53}, priority = {1}, title = {Finite labelling problem in event structures}, url = {http://dx.doi.org/10.1016/0304-3975(94)90065-5}, volume = {123}, year = {1994} }

TY - JOUR ID - citeulike:3582107 L3 - citeulike-article-id:3582107 N2 - In event structures, one of the classical models of parallelism, the concept of nice labelling occurs: this consists in attributing label to each event of the structure, in such a way that two different events may have the same label if either they are in temporal causality or they are not the initial occurrences of incompatible actions. The problem is to minimize the number of labels. In this paper we are concerned with event structures admitting a finite nice labelling. We characterize those admitting a 2-labelling. Then we prove that for finite event structures the optimization of the labelling is an NP-hard problem. Finally, using combinatorial and order-theoretic tools, we investigate some special cases. IS - 1 JF - Theoretical Computer Science SN - 03043975 EP - 19 TI - Finite labelling problem in event structures VL - 123 SP - 9 KW - causality KW - concurrency KW - eventstructure AU - Assous, M PY - 1994/01/17/ UR - http://dx.doi.org/10.1016/0304-3975(94)90065-5 ER -