Complexity Results for POMSET Languages
Joan Feigenbaum, Jeremy A. Kahn, Carsten Lund · SIAM Journal on Discrete Mathematics · 1993
Pratt [Internat. J. Parallel Programming, 15 (1986), pp. 33–7.1] introduced POMSETs (partially ordered multisets) to describe and analyze concurrent systems. A POMSET P gives a set of temporal constraints that any correct execution of a given oncurrent system must satisfy. Let $L ( P )$ (the language ofP) denote the set of all system executions that satisfy the constraints given by P. This paper shows the following for finite POMSETs P, Q, and system execution x: • The POMSET language membership problem (given x and P, is $x \in L( P )$?) is NP-complete. • The POMSET language containment problem (given P and Q, is $L ( P ) \subseteq L ( Q )$?) is $\prod _2^p $-complete. • The POMSET language equality problem (given P and Q, is $L( P ) = L ( Q )$?) is at least as hard as the graph-isomorphism problem. • The POMSET language size problem (given P, how many x are in $L( P )$?) is span-P-complete.