COMPLEXITY RESULTS FOR POMSET LANGUAGES

Pratt Internat. J. Parallel Programming, 15 (1986), pp. 33-71! introd uced POMSETs (partially ordered multisets) to describe and analyze con current systems. A POMSET P gives a set of temporal constraints that a ny correct execution of a given concurrent system must satisfy. Let L( P) (the language of P) denote the set of all system executions that sa tisfy the constraints given by P. This paper shows the following for f inite POMSETs P, Q, and system execution x: The POMSET language member ship problem (given x and P, is x is-an-element-of L(P)?) is NP-comple te. The POMSET language containment problem (given P and Q, is L(P) su bset-or-equal-to L(Q)?) is PI2p-complete. The POMSET language equality problem (given P and Q, is L(P) = L(Q)?) is at least as hard as the g raph-isomorphism problem. The POMSET language size problem (given P, h ow many x are in L(P)?) is span-P-complete.