Charbel Rahhal
email: rahal@loria.fr

Hala Skaf-Molli

Pascal Molli
email: molli@loria.fr

Nishadi De Silva
email: n.desilva@ecs.soton.ac.uk

SemCW: Semantic Collaborative Writing using RST

During collaborative writing each author works on a copy of the shared document. These copies are then merged to produce the final document. This asynchronous work is supported by several collaborative writing tools. While these tools are excellent at merging and detecting syntactic conflicts, they are not able to easily recognise semantic inconsistencies. This hinders the coherence of the document because while each individual copy might be well constructed, they may not be after the merge. To address this, we investigate the combination of the Rhetorical Structure Theory with Operational Transformation approach. In this paper, we define a data model, a set of operations to manipulate the RST structures and a set of transformation functions. A validity checker alerts the authors to areas in the text with possible semantic lapses in the merged documents.

I. INTRODUCTION

Collaborative writing is the process by which several authors work on a document together. The major benefits of collaborative writing include reduced task completion time, reduced errors, and getting different viewpoints and skills [START_REF] Tammaro | Collaborative Writing Is Hard to Support: A Field Study of Collaborative Writing[END_REF], [START_REF] Noël | Empirical study on collaborative writing: What do co-authors do, use, and like?[END_REF]. Various modes of working exist [START_REF] Tammaro | Collaborative Writing Is Hard to Support: A Field Study of Collaborative Writing[END_REF] depending on the proximity and synchronicity of collaborative work. Some groups all work in the same location and on the same time schedule. Other groups work on different schedules and the members may be geographically dispersed. This is common in technical writing scenarios such as the production of research papers by scientists in different countries or institutions.

The disadvantages of collaborative writing include difficult group coordination [START_REF] Noël | Empirical study on collaborative writing: What do co-authors do, use, and like?[END_REF] and documents that are poorly structured [START_REF] Paul Benjamin Lowry | Building a taxonomy and nomenclature of collaborative writing to improve interdisciplinary research and practice[END_REF]. The lack of structure usually arises from misaligned contributions by individual authors. While each section may be well constructed, they may not 'fit' logically when placed together. This is what is referred to as semantic inconsistency in this paper. Worse still, it is often not easy to detect such inconsistencies; thus making many collaboratively authored documents incoherent.

One way of assisting collaborative writing is by using software. There are various tools available today that enable teams of authors to create, update and merge documents [START_REF] Skaf-Molli | New Work Modes for Collaborative Writing[END_REF]. We focus, in particular, on the optimistic replication model since it can support all collaborative interaction modes [START_REF] Skaf-Molli | New Work Modes for Collaborative Writing[END_REF]. In this model, each author has his own copy of the shared data. This has many advantages such as achieving high responsiveness, preserving privacy [START_REF] Sun | Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems[END_REF] and enabling parallel working [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF]. The optimistic replication algorithms deal with concurrency control problems and syntactic inconsistencies. The algorithms ensure that copies of the shared data converge towards a unique value. Therefore, all the authors will have the same value when the system is idle (i.e. no operations in the pipe). While this is important, it does not guarantee that the resulting text is coherent (or semantically sound) [START_REF] De-Silva | Narratives to preserve coherence in collaborative writing[END_REF]. This is true for most of the work done so far in this field; they concentrate mainly on syntactic consistency. Only a few researchers have started handling semantic consistency problems [START_REF] Skaf-Molli | Semantic Consistency for Collaborative Systems[END_REF], [START_REF] Kermarrec | The IceCube Approach to the Reconciliation of Divergent Replicas[END_REF]. In their work, integrity constraints were used to ensure semantic coherence. However, capturing the semantics of a textual document through logical constraints has not been obvious. We realised that special relationships may be needed to define the coherence of a document.

Semantic consistency 1 is a subjective phenomenon. However, for the purposes of this research, we need to narrow down a definition. The ease with which a text can be read and understood can be influenced by several factors such as the grammar, the language and the previous knowledge of the reader. However, assuming all these criteria are fulfilled, it is still possible for a text to not make much sense. Several researchers [START_REF] Hobbs | Towards an understanding of coherence in discourse[END_REF], [START_REF] Mann | Rhetorical structure theory: Toward a functional theory of text organization[END_REF] have established that the coherence of a text is linked to its internal logical structure.

The mere sequence in which the sentences are positioned can influence how the paragraph is interpreted [START_REF] Knott | A Data-Driven Methodology for Motivating a Set of Coherence Relations[END_REF], [START_REF] Marcu | The Theory and Practice of Discourse Parsing and Summarization[END_REF]. For instance, take the two texts below. The first one is easy to understand. However, by just altering the order of the last two sentences, Text 2 has being made less comprehensible. This is because readers tend to assume logical connections between pieces of text in juxtaposition. It is necessary to make these logical connections as easy to determine as possible [START_REF] Zobel | Writing for computer science[END_REF]. Otherwise there is an unnecessary burden placed on the reader.

T ext1 :

Semantic coherence is vital for an effective document. However, current tools do not provide support in this aspect of writing. Therefore, the combination of merging algorithms and RST is a significant step towards bridging this gap.

T ext2 :

1 'Semantic consistency' and 'coherence' are used interchangeably in this paper Semantic coherence is vital for an effective document. Therefore, the combination of merging algorithms and RST is a significant step towards bridging this gap. However, current tools do not provide support in this aspect of writing.

Problems in a short text like the above are easy to identify and fix. In fact, we compose such texts daily in our conversations and e-mails without giving it much thought. However, the problem is much harder to solve in larger documents, particularly when multiple authors are involved.

Linguists who studied the structure of texts have attributed coherence to implicit logical relationships that exist between parts of a text. For instance, part A "provides background information" to part B, part D "provides evidence" to the claim made in part B and so on. So, it is important for authors to establish what these links are before they write and equally important they that convey them to the readers. Linguists also developed theories that enabled authors to study and analyse the logical structure of texts. We believe that using ideas from such a theory will greatly benefit the semantic aspects of collaborative writing. It is support for this aspect of writing that we find missing in collaborative writing tools and is the focus of our work.

In this paper, we provide a brief tutorial on Rhetorical Structure Theory (RST) which is our chosen discourse theory to address semantic consistency. In the section III, we define a data model and a set of operations to edit RST structures. In the section IV, we describe the fundamental principles of merging algorithms through two scenarios. In the section V, we outline Operational Transformation (OT) which is the merging technique we intend to use. In the section VI, we define transformation functions for RST operations. We finally present a possible visual representation of the detection of semantic inconsistency, followed by our conclusions.

II. RHETORICAL STRUCTURE THEORY (RST)

There are several discourse theories that have been developed to analyse the structure and coherence of text. We have chosen Rhetorical Structure Theory (RST) [START_REF] Mann | Rhetorical structure theory: Toward a functional theory of text organization[END_REF] for its simplicity and precise relationship definitions. This section gives a brief description on how to analyse a text using RST and discusses some aspects of the analysis relevant to this paper.

A. Analysing a text using RST

The first step in a RST analysis is to divide the text into non-overlapping segments. Each segment should have independent functional integrity and is often a clause [START_REF] Mann | Rhetorical structure theory: Toward a functional theory of text organization[END_REF]. As an example, Text 1 above has been divided into three segments as shown.

[Text 1:] [Semantic coherence is vital for an effective document.] 1A [However, current tools do not provide support in this aspect of writing.] 1B [Therefore, the combination of merging algorithms and RST is a significant step towards bridging this gap.]1C The next step is to identify logical relationships that exist between pairs of segments. For instance, in the above example, we believe there is a Background relationship between segments A and B (i.e. segment A provides background information to understand segment B). Some relationships are often identified using cue words such as 'however', 'although' and so on [START_REF] Knott | A Data-Driven Methodology for Motivating a Set of Coherence Relations[END_REF], while others can be detected without any such phrases. However, in our application of RST the analyst is also often the author of the text. Therefore, having created the text with a certain understanding of it, we do not anticipate there to be major difficulties in recognising the RST relationships.

Segments in a relationship can play one of two roles: a nucleus or a satellite. A nucleus is considered to be an important segment, essential to the understanding of the text. A satellite is not as critical but does provide supporting material. So, in our BACKGROUND (cf Figure 1) relationship, segment 1A is the satellite and segment 1B is the nucleus. Such relationships involving a nucleus and satellite are called hypotactic and are illustrated as below. Note that the arrowhead points towards the nucleus. [START_REF] Henderson | A narrative approach to collaborative writing: A business process model[END_REF], however, considered 23 to be too many and began selecting a subset of relationships that were sufficient for analysing technical documents. In De Silva [START_REF] De-Silva | A narrative-based collaborative writing tool for constructing coherent technical documents[END_REF], a user study has shown that technical authors found a set of nine relationships adequate for their analyses.

In the analysis, segments involved in a relationship collectively form a span. A span can in turn become part of another relationship as shown below. The span of segments 1A and 1B is identified as being in a Motivation relationship with segment 1C in our example (i.e. the importance of semantic coherence and the lack of support for it has, together, has motivated us to combine existing ideas to solve the problem). Hence, the analysis is a recursive process and continues until all the segments are assembled into a tree of relationships as shown below (called a RS-tree).

Mann and Thompson (1988) conjecture that producing a well-formed RS-tree for a text indicates that a text is coherent. They define four properties that determine if a RS-tree is well formed. They are:

• Completedness One schema application (the root) should • Adjacency Only adjacent text spans/segments can be grouped together to form larger spans. We make use of these properties to test for consistency after changes to a document are merged.

B. The role of RST in collaborative writing

We propose that the co-authors agree on the RST relations between the various sections of the document at the start. This in itself is a useful exercise to iron out differences in the understanding of the 'story' that their document ought to convey. For instance, authors could have differing opinions about what roles the sections should play. Having a wellformed RS-tree for the document also gives the authors some confidence that their document is coherent. Each author then starts work on his assigned section with an understanding of how that section fits in with the rest of the document. This is perhaps the greatest benefit of using RST in this context.

There is a significant difference between this method and traditional applications of RST. Usually, RST is applied to a 'static' text. However, in collaborative writing, the text continually changes. As the text changes, existing RST relationships may no longer apply. Authors too can decide to change the analysis to something they believe is better. In order to accommodate this behavior, we define a validity checker as described in section VI-C.

C. Converting n-ary RS-trees to binary trees

In the analysis above, the RS-tree produced was binary. However, it is common to have n-ary RS-trees (see figure 3).

For the purposes of our research, we restrict RS-trees to be binary. This has been done by other researchers too [START_REF] Marcu | The Theory and Practice of Discourse Parsing and Summarization[END_REF] and makes computations and software implementations easier. The n-ary tree above can easily be converted into a binary tree (cf figure 4).

Fig. 4. A binary RS-tree

There are some decisions that need to be made as to which of the two relationships will appear on top. In this case, we have chosen to have the Motivation on top and the Background at the bottom. It could have been the other way round too. However, in both cases, the sequence of nodes remain the same (i.e. doing a pre-order traversal) and the broad logical structures in both are comparable. In fact, having to make such decisions can be useful too. In our example: Is section C going to provide motivational information for section B only or for both sections A and B, together? So, we do not envisage this to be a problem in our application and continue to use binary trees.

D. Representing RS-trees using URML

To make RST-annotated corpus2 data readable by both humans and computers, an XML format called URML (Underspecified Rhetorical Markup Language) [START_REF] Reitter | Step by step: Underspecified markup in incremental rhetorical analysis[END_REF] was introduced. The benefit of URML is that the entire RST analysis does not have to be known at the time the URML file is created (hence, underspecified). URML allows the RST analysis to be developed incrementally.

As an example, figure 5 shows the URML representation for the RS-tree of figure 2.

<?xml version="1.0" encoding="UTF-8"> <!DOCTYPE urml SYSTEM "urml.dtd"> <urml> <header> <reltypes> <rel name="Background" type="hyp" /> <rel name="Motivation" type="hyp" /> </reltypes> </header> <document id="sample001"> <text> <segment id="1A"> Semantic coherence is vital for an effective document. </segment> <segment id="1B"> However, current tools do not provide support in this aspect of writing. </segment> <segment id="1C"> Therefore, the combination of merging algorithms and RST is a significant step towards bridging this gap.</segment> </text> <analysis status="forest-complete"> <hypRelation id="1-2" type="Background"> <satellite id = "1A" /> <nucleus id ="1B"/> </hypRelation> <hypRelation id="1-3" type="Motivation"> <satellite id= "1-2" /> <nucleus id ="1C"/> </hypRelation> </analysis> </document> </urml>

III. STORING AND EDITING RS-TREES

This section shows how RS-trees can be represented in a data model and also introduces the set of operations that allows authors to edit them.

A. A data model

Looking at the URML above, it becomes clear that a RStree is an ordered sequence of text segments and a set of RST relationships. In order to model RS-trees, we create a data model to store these elements: Segment and Relation.

A segment has the following attributes:

• Position is the position of this segment in the document.

In order to maintain coherence, it is important that the segments are in the correct order. • ID is a unique identifier for each segment given by the system. • Content is the textual content of each segment.

• Visible is a boolean attribute which is true by default and turns to false when the segment is deleted. A segment can also be used to represent a span (an ordered sequence of adjacent segments).

Similarly, a relation has the following attributes:

• ID is a unique identifier for the relation given by the system. • Nucleus is the identifier of the segment that is the nucleus in this relationship. • Satellite is the identifier of the segment that is the satellite (or second nucleus) in this relationship. • Name is the name of the relation such as Motivation or Background. • coveredSegments is a set that contains the positions of the satellite and the nucleus of the relation. It is used in the detection of the violation of the rhetorical properties. Using these two data elements, we proceed now to develop four operations that can be performed on RS-trees.

B. Operations on RS-trees

We introduce the four operations below that can be used to manipulate the RS-trees.

• addSegment(position, id, content, sid) adds a segment in the specified position in the document. sid is the identifier of the site that generates this operation. • delSegment(position) this operation deletes logically a segment at the given position. This means that the segment is marked as invisible. There is no physical deletion for segments to ensure convergence during data reconciliation as we shall see later. • addRelation(Rid, f rom<type, id >, to<type, id">, Rname) operation adds a relationship across the specified segments and groups them into a span. The parameter type is used to indicate if the segment is a nucleus or a satellite. • delRelation(id) this operation deletes the specified relation from the relations set.

IV. MERGING CHANGES TO RS-TREE In this section, we describe the fundamental principles of merging algorithms. These algorithms are based on optimistic replication approach [START_REF] Saito | Optimistic Replication[END_REF]. This approach considers n sites e.g. a user in our context. There is a total order on the identifier of these sites. Each site has a copy of shared data e.g. the URML file in our context. A site modifies its local copy by producing an operation e.g. "add a segment at a given position" in our context. This operation is:

1) executed locally, 2) broadcasted to other sites, 3) received by others sites, 4) integrated locally.

The system is correct if all copies are identical when the system is idle.

In the following sections, we present two scenarios where two authors are modifying in parallel a shared URML document. The URML structure looks like a tree, but in fact we Fig. 6. URML data revisited : Initial state have basically a sequence of segments that represents the text, and a set of relations. We can illustrate the URML data as in figure 6.

A. Concurrent adding scenario

In this scenario, we assume that u 1 and u 2 are editing the T ext1 given in the section I. Each author has his own copy of the T ext1. They both agree on the RST analysis given in figure 6.

Suppose now that u 1 adds a new segment identified by '2' containing the text "XXX" in position 2, between segment '1A' and segment '1B'. The result on the copy of u 1 is as below:

This RS-tree is inconsistent, it violates the connectedness property. The author u 1 has to change his RS-tree as below:

A new relation Motivation has been added by u 1 between '1A' and new segment 2. Old relation "1-2" has been deleted by u 1 and replaced by a relation "1-2'" linking relation 2 and segment '1B'. As old relation "1-2" has been deleted by u 1 , relation "1-3" has been deleted by u 1 and replaced by a relation "1-3'". This way of updating relations is very important for the merging process. This means that the changes performed by u 1 have been detected by the system as the following sequence of operations P 1 :

Of course, we can imagine another scenario where relations are not deleted but just updated. Unfortunately, this scenario is difficult to achieve because operations are traditionally detected using diff algorithms and such algorithms often detect updates as delete operation followed by insert operations. P1={ addSegment(position=2,id=2,content="XXX"); delRelation(1-3); delRelation(1-2); addRelation(id=2,<S,1A>,<N,2>,"Motivation"); addRelation(id=1-2',<S,2>,<N,1B>,"Background"); addRelation(id=1-3',<S,1-2'>,<N,1C>,"Motivation"); } At the same time, the author u 2 on the site2 performs concurrent operations. He adds a new segment identified by '3' containing the text "YYY" in position 2 e.g. between segment '1A' and segment '1B'. The result on the copy of u 2 is: As this state is inconsistent, u 2 adapts the RS-tree as below:

The author u 2 produces the following set of operations: P2={ addSegment(position=2,id=3,content="YYY"); delRelation(1-3); delRelation(1-2); addRelation(id=3,<S,1A>,<N,3>,"SolutionHood"); addRelation(id=1-2'',<S,3>,<N,1B>,"Background"); addRelation(id=1-3',<S,1-2'>,<N,1C>,"Motivation"); }

The execution of the first step of the scenario is illustrated in figure 7. u 1 has generated P 1 and u 2 has generated P 2 , so the copies hosted by u 1 and u 2 are now diverging. Both sites exchange their operations and run the integration process.

In order to converge, the system has to ensure that M erge(P 1, P 2) = M erge(P 2, P 1). Unfortunately, this property is not ensured by traditional merge algorithms. Divergence will occur on segments as depicted in figure below: This problem is well-know in CSCW community. The Operation Transformation (OT) framework [START_REF] Ellis | Concurrency Control in Groupware Systems[END_REF] has been developed to ensure convergence in these conditions.

B. Concurrent add-delete scenario

In this scenario, we assume two authors u 1 and u 2 are editing the initial T ext1. User u 1 adds concurrently a new segment and changes the relations, while user u 2 deletes a segment.

Suppose that u 1 adds a new segment identified by '2' containing the text "XXX" in position 2, between segment '1A' and segment '1B', as in the first scenario. Therefore, he produces the same sequence of operations P 1. The result on the copy of u 1 is as below:

At the same time, the author u 2 concurrently deletes the second segment identified by '1B' and adds a new relation Motivation between 1A and 1C. He produces the following set of operations: P2={ delSegment(1A); delRelation(1-3); delRelation(1-2); addRelation(id=3,<S,1A>,<N,1C>,"Motivation");}

The result on the copy of u 2 is as below:

V. OPERATIONAL TRANSFORMATION APPROACH (OT) The Operational Transformation (OT) approach [START_REF] Ellis | Concurrency Control in Groupware Systems[END_REF] is an optimistic replication model used in the real-time group editors domain. It is a theoretical framework that allows to build a generic and safe synchronizer [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF]. OT considers n sites where each site has a unique identifier and owns a copy of shared data. There is a total order on the sites. When a site performs an update, it generates a corresponding operation, which is first executed locally and then broadcasted to the other sites. Every operation is processed in four steps: (a) generated on one site, (b) broadcasted to the other sites, (c) received by the other sites, (d) executed on the other sites.

The execution context of a received operation op i (step c) may be different from its generation context (step a). In this case, the integration of op i by other sites may lead to inconsistencies between the replicas of data. As an example, we consider two sites -site 1 and site 2 -working on a shared data of type string of characters initially equal to the string "efect". A string of characters can be modified with the operation ins(p,c) for inserting a character c at position p in the string. We assume the position of the first character in a string is 0. User 1 and user 2 generate and execute two concurrent operations op 1 =ins(2,f) and op 2 =ins(5,s), respectively. When op 1 is received and executed on site 2 , it produces the expected string "effects". However, when op 2 is received on site 1 , its execution leads to the state "effecst" since it does not take into account that op 1 has been executed before it. In the end, the copies of site 1 and site 2 do not converge.

In the operational transformation (OT) approach, before being executed, received operations are transformed according to concurrent operations that have already been executed on the local copy. This transformation is performed by calling the appropriate transformation functions.

Definition A transformation function T takes two concurrent operations, op 1 and op 2 , that must be defined on the same state S. The function computes a new operation op 1 equivalent to op 1 (e.g. has the same effects) but defined on the state S = S op 2 . S is the state resulting from the execution of op 2 on state S.

Using OT approach, our previous example is now executed as follows. When op 2 is received on site 1 , op 2 needs to be transformed according to the previously executed operation, op 1 . The integration algorithm calls the transformation function T(op 2 =ins(5,s),op 1 =ins(2,f)) = ins(6,s) = op 2 .

The insertion position of op 2 is incremented since op 1 has inserted an f before s in state "efect". After the execution of op 2 , the state of site 1 becomes "effects". On the contrary, when op 1 is received on site 2 , the transformation does not modify op 1 's parameters since f is inserted before s. Thus, op 1 is executed as-is and the state of site 2 is "effects". In this scenario, OT approach has ensured that both copies converge to the same value.

The OT approach distinguishes two main components: an integration algorithm and a set of transformation functions. The integration algorithm is in charge of reception, diffusion and execution of operations. When necessary, it calls transformation functions. This algorithm does not depend on the type of replicated data. The transformation functions merge concurrent modifications by serializing two concurrent operations. These functions are specific to a particular type of replicated data such as a string of characters [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF], XML documents [START_REF] Oster | Supporting Collaborative Writing of XML Documents[END_REF], calendars or file systems.

OT approach aims to achieve convergence of copies. a) Convergence: Like every optimistic replication algorithm, the OT approach aims to ensure eventual consistency. This means that if no updates are performed for a long period of time, all updates will eventually propagate through the system and all the copies will converge towards the same value. In other words, when the system is idle (no operation in pipes), all the copies become identical.

To ensure convergence, it has been proved [START_REF] Suleiman | Concurrent Operations in a Distributed and Mobile Collaborative Environment[END_REF] that the underlying transformation functions must satisfy two properties:

Definition The TP 1 property defines a state equivalence. The state generated by the execution of op 1 followed by T (op 2 , op 1 ) must be the same as the state generated by the execution of op 2 followed by T (op 1 , op 2 ):

op 1 •T (op 2 , op 1 ) ≡ op 2 •T (op 1 , op 2 )
Definition The TP 2 property ensures that the transformation of an operation regarding a sequence of concurrent operations does not depend on the order in which operations of this sequence were transformed:

T (op 3 , op 1 • T (op 2 , op 1 )) = T (op 3 , op 2 •T (op 1 , op 2 ))
The OT approach could be used to design a reconciliation framework able to reconcile divergent copies of any type of data. In order to build such a framework, the following tasks have to be completed. First, an integration algorithm must be chosen; regarding this algorithm, TP 2 property may be required on underlying transformation functions. Secondly, operations which could be performed on shared data types must be defined. Finally, the required transformation functions for all combinations of operations have to be provided.

We have already used OT to synchronize text [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF] and XML documents [START_REF] Oster | Supporting Collaborative Writing of XML Documents[END_REF]. In this paper, we will use OT to synchronize RS-trees.

VI. SEMCW: MERGING RST DATA WITH OT

OT can be used to manage efficiently the merging of RS-trees. Segments are ordered as a sequence.

A. RST Transformation functions

The following transformation functions deal with concurrent segments operations and ensure convergence.

T (addSegment(n1, id1, v1, sid1), addSegment(n2, id2 v2, sid2)) = if (n1 < n2) or (n1 = n2 and sid1 < sid2) return addSegment(n1, id1, v1, sid1) else return addSegment(n1 + 1, id1, v1, sid1) endif

The above function transforms

op 1 = addSegment(n 1 , id 1 , v 1 , sid 1 ) regarding op 2 = addSegment(n 2 , id 2 , v 2 , sid 2 ).
The main idea is to compare the insertion position of two concurrent addition of segments in the sequence of segments.

• If op 1 inserts a segment at a position after the insertion position of op 2 then the insertion position of op 1 has to be shifted one position to the right. Therefore, its insertion position is incremented. • If op 1 inserts a segment before the insertion position of op 2 then the insertion position of op 1 remains the same. • If op 1 and op 2 insert a segment at the same position, T must decide the serialization order. In the above definition, the decision of T is based on the site identifier.

If the site identifier of op 1 is greater than the site identifier of op 2 then the insertion position of op 1 is shifted one position to the right, else it remains the same. Of course, this an arbitrary choice.

T (delSegment(n1), delSegment(n2)) = if (n1 = n2) return id () else return delSegment(n1) endif
This function transforms op 1 = delSegment(n 1 ) regarding op 2 = delSegment(n 2 ). If op 1 and op 2 delete the same segment, then the function T disables effect of op 1 by transforming it into an identity operation. Else T returns op 1 . In order to ensure the correctness of our transformation functions (that they satisfy TP1 and TP2 properties), we use the TTF approach [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF]. We keep the deleted segment as a tombstone, this means that we keep the segment in its position and mark it as invisible. Consequently, deleted segments must remain present in the model, but are hidden from the user.

T (delSegment(n1), addSegment(n2, id2, v2, sid2)) = if (n1 < n2)
return delSegment(n1) else return delSegment(n1 + 1) endif T (addSegment(n1, id1, v1, sid1), delSegment(n2)) = return addSegment(n1, v1, sid1)

The above transformation functions T (delSegment, addSegment) and T (addSegment, delSegment) are easy to understand.

In fact, the transformation functions for all the remaining couples of operations (e.g. T (delSegment, addRelation), T (addRelation, delSegment), . . .) return the operation itself. Because according to our data model, the relation part of RStree is just a set of relations. Therefore, it is impossible to generate syntactic conflicts by adding or removing relations. Conflicts will occur only at the semantic level.

We need only to define the following transformation function because it is impossible to delete the same relation twice.

T (delRelation(id1), delRelation(id2)) = if (id1 = id2) return id () else return delRelation(id1) endif

B. Scenarios with OT

Now, if we apply OT approach with our transformation functions to the first scenario in the section IV, both sites will converge to the value represented in the figure 8. In the same way, both sites in the second scenario in the section IV will converge to the value represented in the figure 9 As we can see, the final states has both RS-trees, this will help the authors to better understand the reasons of the conflicts. The syntactic convergence is ensured, however, semantic consistency is not ensured. The result does not respect the rhetorical properties. To solve this problem, we developed a validity checker as described in the next section.

C. Validity checker

The merge of two well formed RS-trees is not necessarily a well formed RS-tree.

The main interest of this validity checker is to detect the semantic inconsistency of the document. In other words, the validity checker will detect the violation of the rhetorical properties and informs the user about them. We start by presenting the definition of some elements needed by the validity checker:

• Segments is the ordered sequence of the text segments.

• Relations is the set of all the relations in the RS-trees.

• ConnectViol is the set of the segments violating the connectedness property. For example, if we apply the validity checker to the figure 8, it will traverse the ordered sequence of segments and the set of the relations and checks the violation of each rhetorical property. It will present the following inconsistency:

• Two relations starting from the first segment which violates the uniqueness property. • The second segment is connected in one tree and disconnected in an another tree.

• The third segment is connected in one tree and disconnected in an another tree. • The solutionHood relation violates the adjacency property.

• The 1-2': Background relation violates the adjacency property. • Two relations sibling the fourth segment which violates the uniqueness property. • Two relations sibling the last segment which violates the uniqueness property. • Neither the first tree, nor the second tree respects the completeness property. There exists one segment in each tree not covered by its root. A possible visualization of the validity checker for the example in figure 8 is shown below:

The user has to resolve the conflicts manually. Either by deleting XXX (with the relations) or by deleting YYY (with the relations) or by leaving both texts and replacing the majority of the relations like he is doing a new analysis of the merged text.

VII. RELATED WORK

In the collaborative writing domain, most work on semantic consistency are based on constraints. Skaf-Molli et al. [START_REF] Skaf-Molli | Semantic Consistency for Collaborative Systems[END_REF] propose to integrate these constraints with the OT approach in order to ensure semantic consistency in merged XML documents. If the constraints are violated after merging, the problem is fixed by adding or deleting some actions. In [START_REF] Kermarrec | The IceCube Approach to the Reconciliation of Divergent Replicas[END_REF], semantic consistency is handled as a constraints optimisation problem. If an operation violates the constraints, the operation is canceled. Both the approached in [START_REF] Skaf-Molli | Semantic Consistency for Collaborative Systems[END_REF] and [START_REF] Kermarrec | The IceCube Approach to the Reconciliation of Divergent Replicas[END_REF] bring about lost updates which is not ideal.

Moreover, we are convinced that sometimes it is not possible to capture semantic knowledge by means of constraints. Constraints can define structural elements such as a document having only one title. However, they cannot capture the coauthor's understanding and logical reasoning about the text. Finally, with the constraints approach, the constraints are outside the document. However, with the RST approach, the semantic annotations are part of the document. Therefore, when authors exchange documents, they also pass on their understanding of it via the attached RST relationships.

In previous work regarding coherence in collaborative writing [START_REF] De-Silva | Narratives to preserve coherence in collaborative writing[END_REF], RST was used to analyze an executive summary like outline of the document (called a document narrative). This technique is called narrative-based writing [START_REF] De-Silva | A narrative-based collaborative writing tool for constructing coherent technical documents[END_REF] and enhances the implicit story conveyed by a document to the readers; thereby improving coherence. In this paper, we explore the idea of applying RST directly to the document. The RST relationships help the authors to see the ways in which the sections depend on each other.

The project SALT (Semantically Annotated Latex) has some common features with our work. In [START_REF] Tudor Groza | SALT -Semantically Annotated LaTeX for scientific publications[END_REF], the authors propose a framework for authoring and annotating LaTeX documents. They develop ontology based on RST. The authors add RSTbased semantic tags to their LaTex documents while editing.

In our work, RST is not just used to add semantic annotations within the document but also as a tool to evaluate the document's level of coherence. By constantly maintaining g and checking the four properties, we are able to detect inconsistencies and alert the authors to such areas. We anticipate that we can integrate our work easily into the SALT framework such that our RST capability can be extended into LaTex documents too.

VIII. CONCLUSION AND FUTURE WORKS

This paper described SemCW approach which is the combination of ideas from RST and the OT approach. SemCW allows to detect semantic inconsistency in merged texts. We were motivated to carry out this research after observing a lack of semantic support in collaborative writing tools of today. We envisage that collaboratively produced documents will be annotated with RST relations. As changes are made to the text in the document, these relations need to be changed to communicate the shifts in the narrative goals of the document. Having this understanding of how the text 'works', in our opinion, is the greatest benefit of analyzing the document using RST. The co-authors can then write their individual sections which should, in theory, better fit together.

This paper presented a data model and a set of operations that are necessary for authors to manipulate RS-trees. We also defined transformation functions for each combination of operations so that concurrent operations can be integrated correctly. The validity checker allows to detect semantic inconsistency in the merged document. The visualization at the end showed a possible user interface for this approach.

We believe this work bridges a gap in existing collaborative writing tools. At the moment, these tools handle syntactic conflicts excellently but do not address semantic problems that arise as a result of misaligned contributions by the various authors. RST plays a pivotal role in encouraging authors to think about the underlying logical relationships in their document and the consequences of updates. We realize that appending RST information is not easy and can be seen as cumbersome. However, with more research and experimental evaluation, the process can be made simpler and seamlessly integrated into current tools. We are working now on the definition of an ontology based on the RST and we will use Web Ontology Language (OWL) to detect the violation of RST properties.

Fig. 1 .

 1 Fig. 1. Segment A and B have a Background relationship between them

Fig. 2 .

 2 Fig. 2. A possible RS-tree for Text 1

Fig. 3 .

 3 Fig. 3. An n-ary RS-tree

Fig. 5 .

 5 Fig. 5. URML representation for the RST analysis of Text 1

Fig. 7 .

 7 Fig. 7. Global merging scenario

Fig. 8 .

 8 Fig. 8. URML convergent final state in scenario1

Fig. 9 .

 9 Fig. 9. URML convergent final state in scenario2

1 )

 1 Connectedness violation (∀ S ∈ Segments) [ R ∈ Relations : R.Nucleus = S.ID R.Satellite = S.ID] ⇒ S ∈ ConnectViol. 2) Uniqueness violation (∀ S ∈ Segments) [∃ R, R'∈ Relations: R = R' (R.Satellite = R'.Satellite = S.ID R.Satellite = R'.Nucleus = S.ID R.Nucleus = R'.Nucleus = S.ID R.Nucleus = R'.Satellite = S.ID)] ⇒ S ∈ UniqViol. 3) Adjacency violation (∀ R ∈ Relations) :(R.Satellite.position>R.Nucleus.position+1) (R.Nucleus>R.satellite+1) ⇒ R ∈ AdjViol. 4) Completedness violation (∃ S ∈ Segments){∃ R ∈ Relations : S.position / ∈ R.coveredSegments } {∃ R, R' ∈ relations : R = R' R.coveredSegments = R.coveredSegments covered-Segments = AllTxtSegments)} The checker validity indicates the incoherence parts of the document. It provides the users an awareness about what happened. Based on this knowledge, users are able now to solve the semantic conflicts in a better way.

•

  UniqViol is the set of the segments that violate the uniqueness property.• AdjViol is the set of the relations that violate the adjacency property. • AllTxtSegments is the set containing all the segments' positions of the document.

	• coveredSegments is a set of segments' positions cov-
	ered by a relation. For example, if a relation R has a
	satellite at a position 1 and a nucleus at a position 2,
	then R.coveredSegments ={1,2}. If a relation R has a
	relation R' as satellite and a segment at position 6, then
	R.coveredSegments = R'.coveredSegment	{6}.
	The validity checker detects the violation of each property
	in a simple formal way:

Corpus: A collection of writings or recorded remarks used for linguist analysis


Mayalen Etcheverry

Bert Wang

Clément -Chak Chan

Pierre-Yves Oudeyer

Bert Chan

Clément Moulin-Frier

Meta-Diversity Search in Complex Systems, A Recipe for Artificial Open-Endedness ?

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Problem Formulation

Minecra game environnement is made of building blocks that players can use to construct any structure they desire (also called artifacts) with almost endless possibilities to express their creativity. The blocks exist in a spatio-temporal world which is 3-dimensional in space and where time advances with each gametick.

There is a finite number of possible blocks (M=255) which are described by their type (eg: water, wood, air, etc.) and optionally by a state which further describes the block appearance (eg: texture, orientation) or behavior (eg: age, on/o state, counters).

Let's define the spaces of our problem:

State space : each "cell" of the world (x,y,z) can take a certain state . The visible state in the Evocra API world is limited to the block type .

The hidden state is free of choice, for instance a feature vector can be attached to each "cell" of the world and can describe concrete physical attributes of the cell at this point in space in time (eg: mass or electric currant)

as well as more abstract computational quantities.

Artifact space : an artifact in Minecra (also called phenotype) is represented by its discrete time serie ( for static artifacts) and is a set of elemental blocks where is the block type; is the spatial position; and is the block state.

Search space : each artifact is the result of some sort of design or generative process where a genome determines the artifact initial state as well as the artifact development over time . The choice of the genome and of the generative process (also called genotype-tophenotype mapping) will define the search space and the reachable artifact space of our system.

Solution space : the solution space is set of all possible artifacts which can be generated by .

Following that formalism, our open-ended framework is composed of two main components:

E 1m 3 m s Σ s t j ∈ {1..M } h ∈ R d A a a = {a 0 , … , a t , …} a t = a 0 a t {(m, x, y, z, s)} m (x, y, z) s Θ θ a 0 (a 0 , … , a t ) → a t+1 θ G : Θ → A Θ A W {a ∈ E} G
an artifact-generator which should allow for artifacts with unbounded phenotypic complexity.

an artifact-discovery algorithm that evolves a set of genomes and their corresponding artifacts

( in the open-ended setting) and that should be able to continuously evolve novel and increasingly complex artifacts.

How to artificially construct the genome , the genotype-to-phenotype mapping

Desirata Properties of our Open-Ended Framework

: self-organized system for the endless generation of complex artifacts

We formulate our artifact-generator as an artificial complex system which should comply with the following general properties:

Dynamical system -recursively applies an update rule that changes the state of the system over time.

Growth -the initial state is limited in space and complexity and the phenotype grows and complexifies over time.

G : Θ → A D {(θ 1 , a 1 = G(θ 1 )), … , (θ N , a N = G(θ N ))} ∈ W N → ∞ θ G {(θ, a)} ∈ W G G G f a 0
Local interactions -the update rule is defined on a local neighborhood ball and shared at the di erent locations.

Non-linearity -has non-linear dynamics .

(may be) Open -G might exchange flows of matter/energy with the environment to allow high levels of diversity, heterogeneity and complexity.

(may have a) Memory -G might memorize the system's past states into the hidden features to allow for more advanced behaviors.

The idea of implementing computational systems with the above desirata properties, whose complexity could grow automatically akin to real complex systems is not new. Therefore, a more challenging question is:

Can we automate the long-term discovery of increasingly complex and divergent structures in such systems?

In the same way that Conway's Game of Life together with the community of people searching it might form an example of open-ended system, our open-ended

f G f
framework couples the artifact-generator with an artifact-discovery algorithm able to continuously search for novel and divergent artifacts in .

In the next section, we briefly present the 3 main families of methods that propose to automatically explore the input space of complex systems, namely "naive" strategies (independent of the outcomes of the system), optimization-driven strategies and diversity-driven strategies.

We review why these approaches (in their standard characterization. This limits the scope of the final discoveries: in the same way that the fitness function is constraining the reached area in the observation space , being diverse in a specific does not mean being diverse in . Actually, there is not such thing as a unique ground truth "interesting" diversity in complex phenotypic spaces, and operating in a monolithic BC space might lead to discoveries that are highly-diverse in that space but poorly-diverse according to other potentially-interesting behavioral criteria [Etcheverry et al. 2020].

Meta-Diversity search strategy

To address these limits, we recently formulated the problem of meta-diversity search where an artificial "discovery assistant" incrementally learns divergent

Proposed Implementation

We simulate an artificial "chemistry" system based on Lenia continuous cellular While abstracting away from natural chemistry, we follow this metaphor to illustrate our open-ended system and implementation choices for the challenge.

LeniaChem: an "arti cial chemistry" system

Cellular automata are good models to study how significantly di erent dynamics can arise from uniform simple laws at a smaller scale.

Lenia is a recently proposed cellular automaton that extends traditional CA with continuous state spaces and rules generalized to higher dimensions, multiple kernels and multiple channels. Our variant of Lenia (LeniaChem) used for the Minecra environment is implemented in 3D and combines continuous channels (one channel per "block" in minecra ) and discrete visible states. Any number kernels can be sampled and the kernel matrices are generated with CPPN networks [Stanley, 2007], such that the CA update rule is not limited in its expressive power.

The CA's 3D grid represents the "petri-dish" where evolved patterns will develop in time.

The state space is represented with As an example, [START_REF] Grizou | Cronin -A curious formulation robot enables the discovery of a novel protocell behavior -Science Advances[END_REF] recently propose to explore the dynamics of an oil-droplet system with a "curious robot" which could manipulate the initial mixture composition of chemicals.

The resulting "artifact" here would be the yield of each compound in the final product, the rest being considered as empty "air" invisible blocks in Minecra .

The "physics" formulas of our petri-dish follow Lenia rules [Chan 2020] and apply the following updates to the state at each time step:

1. Loop on all kernel and:

1. calculate the weighted sums with its source channel 2. Apply growth mapping to the weighted sums:

3. Add a small relative portion of the resulting growth to the destination channel:

2. The potentials of each channels are clipped between 0 and 1 3. To prevent participation of empty "air" cells in the update process we apply an alive-masking step [START_REF] Mordvintsev | Di erentiable Self-organizing Systems -Distill[END_REF] as follows: we fix the air potential (channel 0) to a fixed value 0.1 and we consider empty every location which maximum potential is lower than 0.1, by setting every channels (except air's one) to 0.

A t=0 j μ σ dt θ = (ψ, ϕ) f K i→j K i→j * A i A i G i→j = ∑ 2 × e - - 1
((K i→j * A i )-μ) 2 2σ 2 dt * h i→j A j += dt * h i→j * G i→j A j
4. Finally chemical "matter" is created in zones of higher chemical potential with ☝ See videos on: https://mayalene.github.io/evocra search/ Back to the desirata properties of our artifact-generator, LeniaChem is a dynamical system that shows growth, local interactions and non-linearity. LeniaChem is not open in a strictly-speaking sense but we do not impose any sort of massconservation law. Similarly, we do not explicitly implement memory in the CA but any value can be stored in the continuous channel.

Holmes: an arti cial "discovery assistant" exploring the system

To solve the previously-introduced meta-diversity objective, several key challenges need to be addressed. A first challenge is to unsupervisedly learn a diverse set of representations to characterize behaviors and a second challenge is to find a diverse set of patterns in each of those BC spaces.

1) Outer-loop: incremental learning of divergent characterization spaces

To address the first challenge, we use a dynamic neural-network architecture where a hierarchy of module embedding networks is progressively expanded by the discovering agent to characterize the di erent discovered niches of pattern.

The architecture has 4 main components:

(i) a base module embedding neural network (ii) a saturation signal that triggers the instantiating of new nodes in the hierarchy

i BC i BC i R i
The exploration process iterates through steps 1-to-4 as illustrated in the above

Discussion

In the context of such an "open-ended challenge" were the ambitions were also quite "open-ended", we were more or less free to do anything we want. It has been quite fun implementing our ideas in the Minecra environment, but there are many other directions that we could explore for future work.

While we mainly used the Minecra engine as a "renderer" in our current experiments, it will be interesting that our growth process occurs inside the world's physics. Minecra physics are quite poor (most blocks don't even have gravity) but some blocks do have interesting properties and we could also imagine having external sources perturbing the growth process (eg: players throwing blocks inside the petri-dish).

Secondly, it will be interesting to integrate some sort of quality-guidance in the meta-diversity search, for instance by rewarding displacements of the structure's center of mass to hope discovering flying machines in Minecra [START_REF] Grbic | Latent Modules for Exploratory Search in Morphogenetic Systems -NeurIPS[END_REF],

but defining such score might be hard for more complex functionalities (how to reward building a CPU machine?) and might be very di icult to optimize due the sparse reward.

Another type of guidance that would be very interesting to integrate in the discovery process is human-guidance. We have shown in Etcheverry et al. 2020 that minimal feedback from an external user could help the meta-diversity search specialize toward "interesting" types of diversity. What constructions would come out from a community of players guiding the discoveries in distributed parts of the world with their subjective notion of what is "interesting"?

  definition) are limited to comply with open-ended problems and rather tend to converge toward a subregion of the possible solution space . Our artifact-discovery algorithm search objective is formulated as the meta-diversity objective, an extension of the standard diversity objective that we proposed recently in the context of automated discovery in complex systems [Etcheverry et al. 2020]. : meta-diversity search for the endless discovery of novel artifacts Naive search strategy An "naive" strategy consists of covering at best the known search space , for instance with grid-search or uniform sampling strategy . While easy to implement, this is o en very ine icient in covering the space of possible phenotypes, especially for complex genotype-to-phenotype developmental mappings where big regions of the input space are mapped to small regions in the outcome space (we talk of "attractor" states). discovery gets scored with a fitness function and where aims to find individuals with the highest fitness scores . Di erent objectivedriven techniques have been implemented as discovery tool in complex systems

  The objective of this process is to enable continuous seeking of novel source of diversities while being able to quickly adapt the search toward a new unknown type of diversity. Similarly, quality-guidance can be integrated in the framework: with minimal external feedback, a successful discovery assistant should be able to e iciently specialize the exploration strategy toward a particular type of "interesting" diversity, corresponding to the initially unknown preferences of an end-user and expressed through simple sparse feedback.

  automaton [Chan 2019, Chan 2020] and an artificial "discovery assistant" (HOLMES) which integrates a goal-based intrinsically-motivated exploration (inner loop's diversity search) with the incremental learning of a growing hierarchy of behavioral characterization spaces (outer loop's divergent knowledge accumulator) [Etcheverry et al. 2020].

  parameters constraining the range of possible patterns are the grid-size (dimensions of the "petri-dish") and the number of channels (number of "chemical species" represented with blocks in Minecra ). The grid here is a torus, meaning that voxels on the top borders are neighbors to bottom voxels and same for le and right borders. starting material as well as the operating conditions (temperature, pressure, pH, etc.) influencing the development of the final product.

  a boundary criteria that unsupervisedly clusters the incoming patterns into the di erent modules (iv) a connection-scheme that allows feature-wise transfer from a parent module to its children In HOLMES, the clustering of the di erent patterns and the use of learnable connections is central to explore divergent search spaces and to aggregate the knowledge between the distributed modules. While HOLMES architecture is very general, the engineer's choice for the module/connections training strategy and for the clustering algorithm will impact how patterns are separated and distributed into di erent niches, which will in turn greatly influence their "selectivity" by the population-based IMGEP. Here, we use the same implementation choices that in Etcheverry et al. 2020: (i) we use VAEs as base modules : the VAEs are incrementally trained to encode their own niche of patterns into a latent characterization space (ii) we say that the representational capacity of a module saturates when the reconstruction loss of its VAE reaches a plateau (with additional conditions to prevent premature splitting such as minimal node population) (iii) each time a node gets saturated, we freeze its latent space and use K-Means clustering to fit a boundary and redirect the incoming patterns (the boundary is kept fixed for the rest of the exploration) (iv) we instantiate learnable layers called "lateral connections" between the parent and child VAE feature-maps allowing the child VAE to reuse its parent knowledge while learning to characterize novel dissimilar features in its own BC space 2) Inner-loop: nd a diverse set of patterns in each characterization space A goal-based intrinsically-motivated exploration process (IMGEP) is used for the parameter sampling strategy. The IMGEP operates in the hierarchy of goal spaces as defined by HOLMES embedding hierarchy .

R

  (i) sample a target BC space and a target goal in it (the sampling strategy here is equivalent to Novelty Search) (ii) sample a set of parameters for the next rollout to achieve that goal (here nearest neighbor + mutation) (iii) let the system rollout and observe the outcome artifact (iv) store the resulting (parameter, observation, encodings) triplets in an explicit memory (growing archive of all discoveries).ResultingDiscoveries ☝ See full database of discoveries on: https://mayalene.github.io/evocra search/ We show above the resulting discoveries made by IMGEP-HOLMES in the LeniaChem system. Experiments were conducted in 2D ( and ) and in 3D ( ). For 3D artifacts we only show the central slice (z=8) but you can see below a video of what it looks like when projected in Minecra . We conducted growth experiments where patterns are initialized on a small portion of the petri dish (30%), as well a "degrowth" variant where the the petri-dish is filled at t0 by a CPPN-generated pattern. While growth/expansion is one of our desirata for openended systems, the CPPN-generated patterns are visually appealing and produce some sort of decaying art e ect when coupled with the Lenia dynamical system in Minecra , as shown in the second video.

Acknowledgements

This work benefitted from access to the HPC resources of IDRIS under the allocation 2020-[A0091011996] made by GENCI, using the Jean Zay supercomputer.

Resources

The source code used for this challenge can be found at the following link: https://github.com/mayalenE/evocra search/

https://