The complexity of strict serializability revisited (Q1107969)

A well known result by \textit{R. Sethi} [J. Assoc. Comput. Mach. 29, 394- 403 (1982; Zbl 0478.68098)], states that strict view- and final-state serializability are NP-complete in general, but decidable in polynomial time if useless values are absent. This paper falsifies one of these claims by proving that the absence of useless values is not sufficient to make strict final-state serializability decidable in polynomial time. Moreover, we show that a slightly stronger condition is sufficient, namely the absence of dead values. All claim intersection is empty. The algorithm is based on a simple technique for detecting a redundant inequality among a set of inequalities of two variables.