Merging incomparable linearizations

Prefix-intersection merging on L_1 and L_2 gives a linearization L_3 such that L_3 \geq L_1 and L_3 \geq L_2, according to the usual preorder on linearizations. If additionally L_1 and L_2 were incomparable (i.e., L_1 \ngeq L_2 and L_1 \nleq L_2), then L_3 > L_1 and L_3> L_2.

No proof, but I’ve spent a decent amount of CPU time (weeks) on trying to find counterexamples.

Under your total ordering it holds for any of these merge algorithms (including best chunk merging) that L_3 \geq L_1 and L_3 \geq L_2. The surprising part is that prefix-intersection merging seems powerful enough to achieve that under the preorder.

1 Like