98
Proof: We can show thata
1 and a
2 lie between aandbjust as we did in the proof of cases
2 and 3 of Theorem 4.4. It remains to show that if Moved(a, b, S – RecessiveMoves(I, S)),
thenC
X (a
1 , a
2 , S)) = L. The value of any range with paths starting withIwill be determined
by clause 6 of
Definition4.14, and that contents will be determined relative to the change set
S – RecessiveMoves(I, S). However that range will satisfy clause 7, and the value will beL.v
4.5 Summary
This chapter has presented the P-sequence, a representation for the behavior of freely
combining insert, delete, move, and copy changes, and has explored some of its properties.
The P-sequence provides a precise definition of a structure meeting the requirements (and
making the compromises) examined in Chapter 3.
The P-sequence is version-complete for dynamic, permutational changes as described in
Table 2.1. While other sets of dynamic permutational operations are possible, they cannot
represent any more states than Palimpsest’s set does (as discussed in Chapter 3). Since
change-completeness is essentially a variable notion (permitting the maximum number of
useful merge and undo behaviors), I have not attempted to define levels of change-
completeness; they are essentially application dependent. Some other definitions might be
more change-complete than Palimpsest, for some applications. We briefly examined the ex-
tension of the definition of the address ordering to handle conflicted change sets, and saw
that the one effect of conflicted change sets is to break the ordering <
SA . Results are stated
in terms of unconflicted change sets, but they can be trivially extended to conflicted change
sets. When considering models of applications such as real-time editing, where conflict de-
tection is a burden and not an advantage, use of the extended model will be assumed.
Appendix A presents a direct Prolog implementation of the sequence ordering definitions
presented in this chapter. The functions presented there allow concrete instances of Palimp-
Proof: We can show thata
1 and a
2 lie between aandbjust as we did in the proof of cases
2 and 3 of Theorem 4.4. It remains to show that if Moved(a, b, S – RecessiveMoves(I, S)),
thenC
X (a
1 , a
2 , S)) = L. The value of any range with paths starting withIwill be determined
by clause 6 of
Definition4.14, and that contents will be determined relative to the change set
S – RecessiveMoves(I, S). However that range will satisfy clause 7, and the value will beL.v
4.5 Summary
This chapter has presented the P-sequence, a representation for the behavior of freely
combining insert, delete, move, and copy changes, and has explored some of its properties.
The P-sequence provides a precise definition of a structure meeting the requirements (and
making the compromises) examined in Chapter 3.
The P-sequence is version-complete for dynamic, permutational changes as described in
Table 2.1. While other sets of dynamic permutational operations are possible, they cannot
represent any more states than Palimpsest’s set does (as discussed in Chapter 3). Since
change-completeness is essentially a variable notion (permitting the maximum number of
useful merge and undo behaviors), I have not attempted to define levels of change-
completeness; they are essentially application dependent. Some other definitions might be
more change-complete than Palimpsest, for some applications. We briefly examined the ex-
tension of the definition of the address ordering to handle conflicted change sets, and saw
that the one effect of conflicted change sets is to break the ordering <
SA . Results are stated
in terms of unconflicted change sets, but they can be trivially extended to conflicted change
sets. When considering models of applications such as real-time editing, where conflict de-
tection is a burden and not an advantage, use of the extended model will be assumed.
Appendix A presents a direct Prolog implementation of the sequence ordering definitions
presented in this chapter. The functions presented there allow concrete instances of Palimp-
