58
orderingwillnotnecessarilybebasedonatotaltemporalorderingasavailabletosys-
temsthatarenotchange-complete.
Thisstructuraltaxonomyofpotentialzonesofconflictwillallowfocusedconsiderationof
interactingoperationswithouthavingtoexamineeachpossiblestructuralcombinationindi-
vidually,foreachpossiblepairofoperations.Thisisimportantbecausetherearealarge
numberofpossiblepairwiseinteractionsamongevenasmallsetofoperations.Fortunately,
weneednotexhaustivelyexamineallpossiblecases.
3.2 ThePalimpsestsetofbasicsequenceoperations
ThissectiondescribesthebasicoperationschosenforPalimpsest.Iwilldescribethemand
brieflyreviewsomeoftheimplicationsoftheirdefinitionasdynamicoperations.InSection
3.3Iwillexaminetheconflictsthatcanoccurwiththisoperationset,anddevelopsomein-
tuitionastowhatkindsofsolutionsaremostdesirable.InSection3.4,Iconsidertheques-
tionofhowapersistentaddressingmechanismcansimplifytherepresentationandresolu-
tionofconflictsbetweendynamicoperations.WhendescribingPalimpsestoperationsIwill
dependontheabilitytodesignaterangeswithinasequencebymeansofstartandend
points,andtodeterminewhetherapointisinsideoroutsideofsucharange.Sincetheop-
erationsinquestioninfactpermutesequenceelements,andchangetheorderofitems,the
assumptionthatthisispossibleis,strictlyspeaking,unwarranted.Section3.4willredeem
thisassumptionbyshowinghowtousetheinsightsdevelopedinconsideringoperational
conflictresolutiontodefineanappropriatemeaningforsuchanordering.
Palimpsestsequencessupport4primitiveoperations:
• Insert.Thistakesapositioninasequenceandaddsitemstothatsequenceatthatloca-
tion.Apositionisagapbetweentwoitemsofasequence.

59
• Delete.Thistakesarangeofasequence(representedastwopositions)andremovesfrom
thesequenceallitemsbetweenthosetwopositions.
• Move.Thisoperationtakes3positions,tworepresentingthesourcerangeinthese-
quence(justasindelete),andonerepresentingthedestinationofthemove.Amove
operationremovestheelementsinthesourcerange(likedelete),butalsocreatesanew
subsequenceatthedestination.Thissubsequenceisidenticaltowhateverwasdeletedby
themove.
• Copy.Thisoperationtakes3positions(likemove),butdoesnotdeletetheinformation
atitssource.Thesubsequencecreatedbyacopyoperationisalwaysidenticaltothe
sourcerange.
Theseoperationsrepresentthelogicalchangesthattexteditorsperform,andtheediting
modelthatusersapply.Iamnotawareofexperimentalproofofthepropositionthatthe
moveandcopyoperationsarepartofauser’sinternalmodeloftextediting(indeed,Inot
surewhatsuchaproofwouldlooklike).However,thealmostuniversaloccurrenceofthese
termsinthevocabularyofauthors,booksaboutwriting,andeditorialhandbooksisinformal
evidenceoftheirwideacceptanceandpower.Furthermore,thewideacceptanceandpopu-
larityofuserinterfacefeatureslike“DragandDropEditing”inwordprocessingsoftwarealso
supportsthenaturalnessoftheseoperations.Inconflictresolution,too,knowledgeofedit-
ingintentionsprovidesinformationthatcanbeofuseinchoosingareasonableresult.While
thenaturalnessofmoveandcopyisnotdirectlyobservable,theassumptionthattheyare
meaningfulisanimportantmotivationforusingthissetofoperations.
Sofar,Ihavesimplyidentifiedasetofoperationsforrepresentingchangestoasequence
(particularlyasequencerepresentingthetextofadocument).Howdotheseoperationsin-
teractinthecontextofachange-completeeditingsystem,where(ideally)anyindividual
changecanbeincludedin,orexcludedfrom,anarbitraryeditinghistory?Theabilitytoar-
bitrarilyaddachangeisneededinordertoenablemergingtoenabletheforcingofconver-