FINITE LABELING PROBLEM IN EVENT STRUCTURES

In event structures, one of the classical models of parallelism, the c oncept 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 th ey are not the initial occurrences of incompatible actions. The proble m is to minimize the number of labels. In this paper we are concerned with event structures admitting a finite nice labelling. We characteri ze those admitting a 2-labelling. Then we prove that for finite event structures the optimization of the labelling is an NP-hard problem. Fi nally, using combinatorial and order-theoretic tools, we investigate s ome special cases.