Version Variation Visualization (VVV): Case Studies on the Hebrew Haggadah in English

Tom Cheesman (Swansea University) and Avraham Roos (University of Amsterdam)

The 'Version Variation Visualization' project has developed online tools to support comparative, algorithm-assisted investigations of a corpus of multiple versions of a text, e.g. variants, translations, adaptations [START_REF] Cheesman | Reading Originals by the Light of Translations[END_REF][START_REF] Cheesman | Translation Sorting with Eddy and Viv[END_REF][START_REF] Cheesman | Translation Sorting with Eddy and Viv[END_REF][START_REF] Cheesman | Translation Sorting with Eddy and Viv[END_REF]Cheesman et al., -13, 2016;;[START_REF] Thiel | Visualizing Translation Variation: Designing Tools for Literary Scholars in Translation Studies and Linguistics[END_REF]links: www.tinyurl.com/vvvex). A segmenting and aligning tool allows users to 1) define arbitrary segment types, 2) define arbitrary text chunks as segments, and 3) align segments between a 'base text' (a version of the 'original' or translated text), and versions of it. The alignment tool can automatically align recurrent defined segment types in sequence. Several visual interfaces in the prototype installation enable exploratory access to parallel versions, to comparative visual representations of versions' alignment with the base text, and to the base text visually annotated by an algorithmic analysis of variation among versions of segments. Data can be filtered, viewed and exported in diverse ways. Many more modes of access and analysis can be envisaged. The tool is language neutral. Experiments so far mostly use modern texts: German Shakespeare translations. Roos is working on a collection of approx. 100 distinct English-language translations of a Hebrew text with ancient Hebrew and Aramaic passages: the Haggadah [START_REF] Roos | Making a Clean Breast of English Passover Haggadah Translations: Data Visualization of Bowdlerization in Haggadah Translations of Ezekiel[END_REF] 1. The Haggadah On the evening before Passover (Pesach), Jews gather at home to celebrate a festive ceremony and meal with family and friends, to commemorate the biblical Exodus of the Jewish people out of Egypt. They eat the traditional matza, drink the prescribed four glasses of wine, and read from the Haggadah. This is a Hebrew text with instructions for a 15-phase ceremony: what to say or sing, which acts to perform, in what order, when to eat or drink what, etc. All participants hold a printed copy of the Haggadah. Typically, many different versions (plural: Haggadot) are present in the room.

The Hebrew Haggadah text is a compilation of Bible quotes, excerpts from traditional rabbinical teachings (Mishnah, Midrash), Exodus narrative, explanations of the festival's history, and Passover 'laws'. The text probably dates back to 200-300 CE. The oldest complete manuscript dates to the 10th century CE. Thousands of variant Hebrew-language versions are extant, in manuscript and print. There are translations in over 40 different languages [START_REF] Yudlov | ' --it ha-defus ha-ʻivri ʻ[END_REF]. The first English-language version appeared in London in 1770. Countless more have since appeared. [START_REF] Yudlov | ' --it ha-defus ha-ʻivri ʻ[END_REF] catalogues 823 English-language editions to 1960. The rate of production of new ones has since been accelerating exponentially. Most of these are retranslations, variously dependent on precursors.

Roos is compiling a digital corpus of English-language Haggadah translations, and using digital tools to compare them and visualize the differences. He aims to explain the differences in terms of their cultural historical contexts, and so shed light on translators' minds and motives.

Version Variation Visualization (VVV): Eddy and Viv Algorithms

VVV compares multiple retranslation documents at segment level, and visualizes the similarities and differences, in order to facilitate overviews, close reading, and navigation among versions. An algorithm called 'Eddy' ('∑D') quantifies variation among versions of a base text segment, in order to distinguish more and less predictable or distinctive versions. An algorithm called Viv ('variation in variation') aggregates Eddy metrics, and projects the result onto the base text segment, in order to distinguish more and less variously translated segments. The algorithms can be applied to the aligned corpus or any selected sub-corpus.

Eddy

The Eddy value assigned to a particular version or section indicates its "strangeness" as compared to other versions. Essentially, Eddy assigns lower metrics to wordings which are closer to the notional average, and higher metrics to more distant ones. So, Eddy ranks versions on a cline from low to high distinctiveness, or originality, or unpredictability. It sorts common-or-garden translations from interestingly different ones.

Eddy can be implemented in various ways. Our standard approach is: Each word in the corpus word list [where corpus means the corpus of aligned segment versions] is considered as representing an axis in N-dimensional space, where N is the length of the corpus word list. For each version, a point is plotted within this space whose co-ordinates are given by the word frequencies in the version word list for that version. (Words not used in that version have a frequency of zero.) The position of a notional 'average' translation is established by finding the centroid of that set of points. An initial 'Eddy' variation value for each version is calculated by measuring the Euclidean distance between the point for that version and the centroid. (Flanagan in: [START_REF] Cheesman | Translation Array Prototype 1: Project Overview[END_REF] No stop words are excluded; no stemming, lemmatisation or parsing is performed. Users can also select a more primitive arithmetical formula, and one using Dice's co-efficient.

In the VVV 'Eddy and Viv' view, when a base text segment is selected, the segment-versions are displayed in a scrollable list in Eddy order, with associated metrics, and with a visual representation of relative Eddy value. The list can be re-ordered to display by date, translator name, or segment length in characters. Eddy values can also be displayed, explored, and exported in the form of charts and tables.

Examples of Eddy use will be provided in section 4.1.

Viv

Viv aggregates the Eddy values for a segment. In our standard approach, Viv is the average of Eddy values of version-segments. Users can also select Viv as the standard deviation of Eddy values. Viv indicates where translators differed most or least, in relation to the base text. (This function is comparable with the amount of layering associated with a word or string of words in the TRAViz visualization: [START_REF] Jänicke | TRAViz: A Visualization for Variant Graphs[END_REF] In the VVV 'Eddy and Viv' view, Viv is represented on the base text by a tonal underlay , varying with the relative value of each segment. Metrics can be viewed by brushing a segment. Floor and ceiling values can be altered to facilitate surveying the base text.

Segments can be filtered in various ways (text search, Eddy/Viv ranges, segment lengths, etc), in the base text and in the version corpus or subcorpora, and texts exported in CSV tables with associated Eddy and Viv metrics.

Examples of Viv use will be provided in section 4.3.

As one reviewer commented, Eddy/Viv is not the only possible approach to comparing differing translations/versions. Measuring the overlap of words (or lemmas) among segments would achieve the same effect. Such a method would also need to calculate a centroid and distances from it.

VVV is specifically created to compare numerous retranslations of the same source text, making it ideal for research into Haggadah version variation. It can help a researcher identify variations, and present them to an audience.

Related Work

There has been some digital work on larger retranslations corpora, involving works of wide intrinsic interest, but none designed to facilitate access to multiple translations, and the translated work, together with algorithmic analyses. Janicke et al. ( 2015) take an in some ways similar approach, but their 'TRAViz' interface offers a very different mode of text visualization, is monolingual (shows no translated text), and works best with more limited variation and shorter texts. Similarly, Juxta-Commons, CollateX and Stemmaweb are monolingual, do not rate the "strangeness" of variants in comparison to all others (Eddy value) and do not create a heat map in the source text (Viv Value) revealing which ST instances generated most target text variants, two of the most powerful VVV features. It is especially these comparisons between the ST and the TT that this research focuses on. Whereas the above software highlights differences in the versions, VVV highlights how these differences are connected to the ST, thus helping us the explain the reasons for the variants.

Lapshinova-Koltunski (2013) describes a parallel multi-translation corpus designed to support computational linguistic analyses of differences between professional translations, student translations, MT outputs and edited MT outputs. Shei and Pain (2002) proposed a similar parallel corpus, with an interface designed for translator training. These projects only offer access to filtered segments of the text corpus, and do not envisage exploring variation among retranslations. Altintas, Can, and Patton (2007) used two time-separated (c.1950, c.2000) collections of published translations of the same seven English, French or Russian literary classics into Turkish, in order to quantify aspects of language change. This raises the question whether such translations 'represent' their language. Corpus-based Translation Studies (Baker, 1993;Kruger et al., 2011) has established that translated language differs from untranslated language. We also know from decades of work in Descriptive Translation Studies (Morini, 2014;Toury, 2012) that retranslations vary for complex genre-, market-, subculture-specific and institutional factors, and individual psychosocial factors, involving the translators and others with a hand in the work (commissioners, editors), and their uses of resources including source versions and prior (re)translations.

Using VVV with Haggadah Samples

One section of the Haggadah concerns four sons who represent four different attitudes to Judaism. Each asks a question which characterizes their attitude, and the text suggests how to respond to these questions. The Hebrew text has 126 words and is divided into six parts: (1) introduction; (2) characterization of the four sons; (3)-( 6) one paragraph for each son, with his question and the response. 60 different translations were uploaded to VVV, segmented and manually aligned with the Hebrew base text. Each translation contains between five and twelve manually defined segments: units of meaning.

Exploring with Eddy

In part (2), characterizing the four sons, most translators use straightforward terms: 'wise', 'wicked', 'simple', and 'one who does not know how to ask'. Some are more creative. Eddy highlights certain translations as 'strange'. VVV automatically rates each version, thus ranking all 60 versions from most common to most exotic. In The corpus includes C18 and C19 versions, but none appear in this table. Almost all high Eddy versions date from the 1940s and after. The general retranslation trend is towards greater variation, probably at least in part because of copyright issues and a need to differentiate in order to stand out in the ever growing crowd.

As a distant reading tool, VVV's Eddy values reveals to us that in comparison to other versions of the same period, the 1906 translation (WILROS) is an early outlier, therefore worth further investigation. Close reading reveals that the language use in this particular translation is indeed quite extraordinary, with phrases such as "Israel's exode from Egypt", "and took cognizance of them", "of which Jerusalem is emblematic", "cut the sea in twain", etc. Historically and culturally, William Rosenau was a radical leader of Reform Judaism, and he would eventually edit the revised edition of the Reform Union Haggadah, with a thoroughly rewritten source text. The version in our corpus still adheres to the traditional ST, but Rosenau's radicalism clearly shines through in his translation and is picked up by VVV.

It is also intriguing that no version is consistently in the highest 5 for all four sons (see

Eddy Variation Chart

The poet Abraham Regelson published several Haggadot. Roos's collection includes one from 1944 (REGFORST1) and another from 1952 (REGFORST2). VVV's Variation Chart ('Eddy Overview') helps us compare these two translations (see Figure 1). This chart plots each version's Eddy values on the y-axis, for segments in sequence on the x-axis. The user can select which versions' graphs to display or hide, select an area to zoom in on, and hover over a node to display base text and version (as is shown in Figure 1). In Figure 1 we see Regelson using higher Eddy-value language (more distinctive language in relation to the corpus) in 1952 than in 1944. One exception is highlighted, in part (2) of the passage (discussed in Section 3.3). For me, and not for him -had he been there, he would not have been redeemed.

What says the Simple Son? -"What is all this about?" Therefore, say to him: "With might of hand, the Lord hath taken us out of Egypt, from the house of slavery."

But the One Who Wits Not To Ask-sit is for thee to open talk with him, as it is said: "And thou shalt tell thy son on that day, saying: 'This is on account of what the Lord did for me when I went forth from Egypt.''' Praised be God, praised be He. Blessed be He who gave the Torah to His people, Israel. Blessed be He. On the subject of the Passover service the Torah speaks of -FOUR SONS One is intelligent, one is ill-mannered, one is indifferent, and one is not even able to ask a question.

1. The INTELLIGENT son asks: "What is the meaning of all the Passover customs and ceremonies, the rules and rites which God has commanded?" You will explain to him all the traditions of Pesach down to the last detail of the Afikoman.

2. The ILL-MANNERED one asks: "What's the sense of all this business of yours?" Yours, he says; and none of his. By refusing to identify himself with his people he denies a basic principle of our religion. You may fling this in his teeth: "I do this because of what the Lord did for me when He rescued me from Egypt." Me not him. Let him know that had he been there, by denying his brothers he could not have been saved.

3. The INDIFFERENT one merely asks: "What is this?" Tell him: "With a strong hand God took us out of Egypt where we were slaves."

4. The INCOMPETENT one-get him started by quoting the words from the Bible: "In that day you shall tell your son saying: (Point to the ceremonial dishes.) "All of this is because of what the Lord did for me when I came out of Egypt."

It makes sense to assume that, having in 1944 already translated the Haggadah in a quite straightforward manner, Regelson decided for the 1952 translation to try out different translation techniques, more off the beaten path. That would explain why his 1952 translation scores higher Eddy values. Examples of this can be seen by the alliterated names of the four sons (Intelligent, ill-mannered, indifferent, and incompetent), something not found in any of the other versions. On the other hand, having used a etymology-based final comment for the wise son in 1944, Regelson opts for a very specific Jewish-sources based closing for his 1952 intelligent son. We will comment on this further in the next section.

Viv: Variation in Variation

In VVV's 'Eddy and Viv' interface, base text segments are highlighted according to their Viv value: the higher the value, the darker the underlay tone. We can visually identify which base text segments produced the most variant translations, or 'read the original by the light of the translations' [START_REF] Cheesman | Reading Originals by the Light of Translations[END_REF]. What does the wise [son] say? 'What are these testimonies, statutes and judgments that the Lord our God commanded you?' (Deuteronomy 6:20) And accordingly you will say to him, as per the laws of the Pesach sacrifice, 'We may not eat an afikoman [a dessert or other foods eaten after the meal] after [we are finished eating] the Pesach sacrifice.' (Sefaria website, www.sefaria.org, 2014) The segment with highest Viv value is the one beginning: 'We may not eat an afikoman…'. This is a quote from the Mishna (oral laws compiled about 200 CE by Rabbi Judah HaNasi, the basis for the later Talmud). Already in the Talmud (c. 500 CE) the correct meaning of the term afikoman had become obscure and was disputed. In Talmudic traditions, afikoman (Hebrew )אפיקומן is said to derive from Greek epikomen or epikomion (επί Κομός), 'that which comes after', variously interpreted as (A) 'dessert', or (B) 'after-dinner entertainment/revelry', and additionally as (C) a metaphor.

There are five common interpretations in the context of the wise son: (A1) any proscribed dessert; (A2) the specific prescribed dessert at stage 13 of Passover (the piece of a matza which is broken in two during stage 4); (B1) proscribed excessive subsequent entertainment (distinguishing Passover from pagan celebrations); (C1) prescribed teaching of all of the (Passover) law: because the afikoman is the last law in the section on Pesach, so "We don't leave anything until after the afikoman" could mean, "we don't stop studying until we have learned everything"; (C2) prescribed sacrifice of a Passover lamb. There is also a sixth option for translation: leaving afikoman to stand in the target text, uninterpreted. This range of options explains the segment's high Viv value. Some of the variant English versions, low in the Eddy value list, are shown in the VVV 'Eddy and Viv' view in Figure 2.

Figure 2. Eddy and Viv view of Haggadah Four Sons passage

Recall Figure 1. In this segment, Regelson first (in 1944) opted for 'afternoon entertainment' (interpretation B). That has quite high Eddy value: it's a less popular translation. In 1952 he switched to the version seen in Figure 2: 'down to the last detail of the afikoman' (interpretation C1). This has a much lower Eddy value than the 1944 option: in this instance, Regelson's later Haggadah made a commoner translation choice. It might be that this decision was influenced by the fact that more and more translators by that time interpreted afikoman in a metaphoric manner.

Viv and Eddy values are calculated according to manually set segments (meaningful units). These can be single words, phrases, sentences, paragraphs or even the whole text. By creating a whole text segment, one could easily aggregate data for a quantitative comparison of whole texts. This way, although no one version consistently deviates from the norm for all 4 sons (as shown above), it is possible to ascertain which translation as a whole is furthest from the base texts. It should be noted, however, that by doing this, the Viv value becomes irrelevant. The version that scored the highest overall Eddy value was the 1974 Polychrome Haggadah by Jacob Freedman, whose translation is extremely verbose and elaborate. 1) expands to an extraordinary degree. The 1955 and 1967 versions are also expansive. They did not appear in Table 1. Figure 3 now explains why: both omit the segments which name the four sons, shown in Table 1.

The

Conclusions

Using VVV can yield valuable insights when comparing multiple variants, and is also useful for presenting findings visually. Manually comparing different versions becomes difficult with larger corpora. When Viv is highlighted in base text segments, even researchers with no knowledge of a language (in this case Hebrew) can identify the parts that warrant closer inspection.

VVV offers a useful range of visualization modes, but many more can be developed. Future research planned on the Haggadah includes comparing the language use of translators when translating Hebrew and Aramaic text passages, comparing the translations of biblical Hebrew versus more modern Hebrew text passages, and translated transitive versus intransitive verb forms.

Thanks

We would like to thank VVV developer Kevin Flanagan for continuing technical support, and Eran Hadas for his endeavors to streamline uploading and segmenting texts in VVV.

Figure 1 .

 1 Figure 1. Comparing REGFORST1 and REGFORST2 in the Eddy Variation Chart Let us compare (close read) these two Regelson versions:

Figure 2

 2 Figure 2 depicts a selection from an 'Eddy and Viv' view of the 'Four Sons' passage. The six parts are shown as paragraphs. Viv underlay tones indicate that the segments with the highest Viv value are within part (3), the 'wise' son, and part (4), the 'wicked' son. Most of part (4) has very low Viv value. Part (2), giving the sons' names, also has very low Viv value.

Figure 2 .

 2 Figure 2. Partial Screenshot of Eddy and Viv view of Haggadah 'Four Sons' Passage This focuses our attention on the highest Viv segment: the answer to the wise son's question. Here the Hebrew text of part (3) is followed by a recent, scholarly English version, including commentary:

  Viv 4.4 Parallel View Visualization: Alignment Maps Parallel view visualizations include a distant overview of segment alignments between base text and versions: an 'alignment map'. Successive segments of the base text are represented as a vertical 'barcode': the thickness of a bar represents segment length in words. Segments of a version are represented in the same format. Alignments are represented by lines connecting base text and version. This enables rapid identification of translators' editing decisions: omission, addition, reduction, expansion, and transposition.

Figure 3 (Figure 3 .

 33 Figure 3 (created from screenshots) shows ten examples of the 'Four Sons' passage. The unchanging base text is on the left, the version on the right of each 'map'. The afikoman segment is highlighted.

TABLE 1 . Names of the Four Sons: Translations with Lowest and Highest Eddy

 1 Table 1, the left column gives the original Hebrew and the commonest translation (lowest Eddy value). The second column gives the five translations with highest Eddy values (rounded Eddy figures given in column 3): outliers in comparison to all other versions in the corpus, worth further exploration.

	Base text and
	lowest translation	Eddy	5 highest Eddy translations	Eddy value	Version reference	Version date
					One is intelligent	1.28 REGFORST2 1952
	חכם	אחד	One is understanding	1.30 POLYHH	1974
	One wise				The intelligent child	1.38 WILROS	1906
					A clever son	1.45 TCH	1954
					The first is sensible	1.52 MSAM	1942
					The second mean	1.38 MSAM	1942
	רשע	ואחד	The rebellious child	1.38 ANIM	2005
	One wicked			One is ill-mannered	1.50 REGFORST2 1952
					and one who is stubborn	1.63 GUT	1956

Table 2

 2

	). A translation's relative Eddy varies, as we will see in the next section.
	son1 REGFORST2 POLYHH TCH WILROS MSAM

TABLE 2 . Highest Eddy Scorers from Table 1

 2

Funding

The VVV project was supported in 2011-13 by Swansea University (Research Incentive Fund and Bridging the Gaps). The main phase of software development was funded by a 6-month Research Development Grant under the Digital Transformations theme of the Arts and Humanities Research Council (UK), reference AH/J012483/1, in 2012.


1 Notation

E : space under study; x, y points of E; P(E) : set of the subsets of E, also called classes; S, A : classes of E; T j the sibling classes of S; π = π(E) : partition of E; π(S) : partial partition ( in short p.p.) of support S ∈ P(E)); the notation τ (S) is also used for p.p.

{S} p.p. with unique class S (when there is no ambiguity, {S} is just written S) ; D(E) set of all p.p. for all supports S ∈ P(E); ≤, ∧, ∨: when applied to partitions, are relative to the refinement ordering; : concatenation of classes and p.p. i.e. π(S) = S 1 S 2 ⇔ S 1 ∪ S 2 = S and S 1 ∩ S 2 = ∅; H = {π i , i ∈ I}: hierarchy, i.e. family of increasing partitions; S = S(H) family of all classes of H; cut π: partition of E into classes taken in H; Π(E) set of all partitions of E, which is a lattice for the refinement ordering; Π(E, H) set of all cuts of H, viewed as a lattice for the refinement ordering; ω: energy, i.e. scalar function on D(E); ω , ω , ω : ω-energetic ordering, infimum, and supremum, w.r.t. energy ω; Π(ω, H): ω-energetic lattice on the cuts of H; π * minimal cut in an energetic lattice.

Reminder on Partitions

Partition Intuitively, a partition π, or π(E), is a division of image domain E into classes which are pair-wise disjoint and whose union restores E in its entirety. Definition 1. A partition π of the image domain E is a family of sets S:

π = {S ⊆ E} (1)
where S : E → P(E), and for each point x ∈ E, we have x ∈ S(x), and

x, y ∈ E ⇒ S(x) = S(y) or S(x) ∩ S(y) = ∅

These S are called the classes of the partition π

Refinement order and lattice The set of all partitions π of E forms a complete lattice Π(E) for the partial ordering of the refinement, where π i ≤ π j when each class S i (x) of π i is included in the class S j (x) of π j at the same point x ∈ E:

π i ≤ π j ⇔ S i (x) ⊆ S j (x). (3)
This refinement lattice is denoted by Π(E). The refinement infimum of a family {π i , i ∈ I ⊆ R} in Π(E) is the partition π whose class at point x is ∩S i (x), and the refinement supremum is the finest partition π such that S i (x) ⊆ S (x) for all i ∈ I and x ∈ E.

Partial partition First introduced by Ronse in [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF], a partial partition is a local partitioning of a subset S ⊆ E of the input space. Definition 2. A partial partition π(S) of support S ∈ P(E) is a set,

π(S) = {A i |A i ⊆ S, A i ∩ A j = ∅} = π {S} (4)
where S = ∪A i , is called the support of partial partition π(S).

Partial partitions appear in figure 3, for example. The restriction of partition π to those classes whose union forms the set S is denoted by π(S) = π {S}, and the partial partition of S into the single class S is denoted by {S}.

Energy An energy ω is a real valued function over the family of partial partitions D(E) of space E: ω :

D(E) → R (5)
When the energy ω of a p.p. is the sum of the energies of its classes, then ω is said to be linear [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF] [START_REF] Guigues | Scale-Sets Image Analysis[END_REF] ω(π(S)) =

T i ∈π(S) ω(T i ) (6)
3 Reminder on Hierarchies of partitions Hierarchy Hierarchies of partitions are the matter of an abundant literature (see for example [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], [START_REF] Meyer | Adjunctions on the lattice of dendrograms[END_REF]). The definition that we propose here is based on two axioms: Definition 3. (Hierarchy of Partitions(HOP)) A family {π i , i ∈ I ⊆ Z} of partitions of E defines a hierarchy when, 1. The partitions π i are nested, i.e. they form a chain for the refinement ordering:

H = {π i , i ∈ I} with i ≤ k ⇒ π i ≤ π k , I ⊆ Z, (7)
where the finest partition π 0 is called the leaves, and the coarsest one, is the root;

2. The number of leaves is finite in any class of the hierarchy, except possibly, in the class {E}.

One often takes the whole space {E} for the root.

Classes and cuts A hierarchy can be described from its classes, or nodes. At each point

x ∈ E the family of all classes S i (x) containing x forms a closed chain of nested elements in P(E), from the leave S 0 (x) to E. This chain is called the cone at point x. Let S ={S i (x), x ∈ E, i ∈ I} be the family of all classes of H. Class S is characterized by the implication i ≤ j and x, y ∈ E ⇒ S i (x) ⊆ S j (y), or S i (x) ⊇ S j (y), or S i (x) ∩ S j (y) = ∅.

which generalizes the characterization (2) of the partitions. The classes of the partition π i-1 included in the class S i of the partition π i are the sons or the siblings of S i , and hierarchy is said to be binary when each class has two sons exactly. The symbol refers to the disjoint union of classes, i.e.

S = S 1 S 2 ⇔ S 1 ∪ S 2 = S and S 1 ∩ S 2 = ∅.
A cut of H is a partition of the space E into classes taken in S. The symbol Π(E, H) stands for the set of all cuts of H. Clearly, Π(E, H) is a sub-lattice of Π(E), the lattice of all partitions of E. If S ∈ S(H), then Π(S, H) denotes the family of all partial partitions of S whose classes are in S(H).

CART and cuts of minimal energy Classification and Regression Trees (CART) were introduced in the 80's by Breiman et al [6], which creates powerful and simple binary tree based models for classification and regression problems, in statistical learning theory. The method consisted in creating rectangular partition of a feature space (high dimensional R n ), either fit a model over each of these rectangles in case of regression, produce a classification. These trees (now called decision trees) described then the estimator for the regression function, or a linear separator for classification tasks.

Salembier-Garrido and Guigues [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF] [START_REF] Guigues | Scale-Sets Image Analysis[END_REF] generalized the CART framework to families of partitions obtained from image segmentations 1 . The first two study binary partition trees, i.e. hierarchies of partitions created by using the max-tree representation, while Guigues considers a hierarchy created from complete linkage on regions of an over-segmentation [13], titled as Cocoons. In both studies a so called "dynamic programing" is used to find a cut of minimal energy, according to the rule described on the toy example of Figure

Discussion

The main features of these approaches, from Breiman to Guigues, set a few questions:

1-Number of cuts The principle of the method consists in allocating an energy with each cut, then to minimize the energy, and to state that the minimal energy characterizes a minimal cut. Now consider a binary hierarchy H of n = 2 p leaves, where p is the number of levels. This hierarchy H generates more 2 2 P -1 cuts. For example, in a small binary hierarchy of six levels, n = 64, and one finds 10 11,3 cuts, i.e. more than 100 times the population of the earth in 2013 (namely 7, 125 × 10 9 persons). A basis of n = 512 leaves, which is common in image processing, provides 10 90 cuts, a number equal to that of all the particles of the universe... Can we really match a scalar energy with so many cuts?

2-An absent energy Moreover, though an energy is "officially" given to each cut, is it really used in the dynamic programing for minimization? The global energies of the cuts never appear during the processing, which just needs local energies to locally compare the cuts, and results in a global minimal cut whose energy is ususlly ignored. Here is an example. Imagine an infinite set of leaves covering the whole plane R 2 , like a huge chessboard, and a hierarchy H where all classes but the last one, E, admit a finite number of leaves. Take an additive energy ω equal to 1 on every class, and +∞ for E. Then all cuts have an infinite energy, whereas the dynamic programing of figure ?? still works perfectly well. It is the concern of partial partitions, indeed, and it never needs the energy of the complete cuts to compare them. Again, the notion which is minimized should not be the energy of the cut. Breiman' work,[6] where the energy of a partial partition is the sum of the energies of its constituent classes, most of the authors have adopted this linearity [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF] [12] [START_REF] Guigues | Scale-Sets Image Analysis[END_REF]. However other laws of compositions appear in literature, e.g. by supremum [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], [START_REF] Akcay | Automatic detection of geospatial objects using multiple hierarchical segmentations[END_REF], [START_REF] Valero | Hyperspectral image representation and Processing with Binary Partition Trees[END_REF], or by infimum [START_REF] Kiran | Fusions of Ground Truths and of Hierarchies of Segmentations[END_REF]. How to regroup all these modalities in a unique notion ?

3-Linearity Following

4-Hierarchies only?

The dynamic programing exclusively requires the comparison between fathers and siblings. It never imposes that a father has a unique set of siblings, i.e. that we are working with a hierarchy. Could we introduce classes which would present several decompositions into partial partitions?

These four comments govern the theoretical development which follows. Dynamic programing opens the way to the energetic ordering; the discrepancy between the numbers of cuts and of energies drives us to energetic lattice; the extension of the linearity directly leads to h-increasingness; and the braids turn out to generalize hierarchies.

Braid

To define the braids, we start from the lattice Π(E) of the partitions of E, of minimal element the leaves partition π 0 . Next we introduce a hierarchy H which serves as a parameter. A braid B is a family of partitions of E. The family B is not arbitrary, but monitored by a non-trivial hierarchy H, in the sense that the refinement supremum of any two elements of Π(E, B) is a cut of H. This leads to the more formal definition: Definition 4. (Braid of Partitions) Let Π(E) be the complete lattice of all partitions of set E; let H be a hierarchy in Π(E). A braid B of monitor H is a family in Π(E) where the refinement supremum of any pair π 1 , π 2 in B is a cut of H, other than {E}, and belongs to Π(E, H) \ {E}:

∀π 1 , π 2 ∈ B ⇒ π 1 ∨ π 2 ∈ Π(E, H) \ {E} (9)
The partition with one class {E} is not considered in Equation 9, since this would imply that any family of arbitrary partitions would form a braid with {E} as supremum, thus losing any useful structure. We also assume a locally finite number of classes in such cases, like in the case of hierarchies. Though the classes of supremums π 1 ∨ π 2 are classes of monitor hierarchy H, the monitor by itself is not uniquely defined.

Cuts in braids Just as for the cuts of H, which were denoted by Π(E, H), we now define the cuts of B as the partitions whose classes are taken in B, and denote the class of all these cuts by Π(E, B).The hierarchy H may itself belong to the braid, or not. On the other hand, any hierarchy is a braid with itself as monitor. When H ⊆ B, we have Π(E, H) ⊆ Π(E, B) ⊆ Π(E), i.e. the braid cuts Π(E, B) are in between the cuts of the hierarchy H and the set of all partitions of E. A braid cannot be represented by a saliency, except when it reduces to a hierarchy whose classes are connected sets.

Braids and hierarchies

The braids of partitions (BOP) provide alternatives to hierarchical structure in many ways. We state one direction here, where a composition law on tuples of hierarchies produces a braid. Proposition 5. Given three hierarchies H, H 1 , H 2 formed from the same leaves, such that, H 1 ≤ H, H 2 ≤ H, then the family of partitions given by {H 1 ∪ H 2 } \ {E} forms a braid with the monitor H.

Here H 1 ≤ H on hierarchies says that each class of hierarchy H 1 is contained in the classes of H. The union of hierarchies form braids, while braids are not necessarily decomposable into hierarchies. This property characterizes the braids without making explicit the monitor hierarchy, and can be useful as a starting point. It is illustrated by Figure 2 6 h-increasing energies An energy ω ≥ 0 on p.p. may not lend itself to dynamic programing. For example, take for energy ω(π) = 1 (resp. 2) when the number of classes of the p.p. π is 1 (resp. 2), and ω(π) = 0 otherwise. Then, as shown in Figure 5 b and c, one finds two cuts of minimal energy, and none of them is reached by dynamic programing. The condition missed by this counter example is that of h-increasingness. It is a property of the energies ω on partial partitions D(E) which preserves the optimal substructure [START_REF] Serra | Hierarchy and Optima, in Discrete Geometry for Computer Imagery[END_REF] [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF].

Cones of the monitor

h-increasingness is involved in three aspects of the theory. Firstly it serves as corner stone in the construction of energetic lattices, secondly it governs dynamic program for extracting minimal cuts, and, finally, it permits the global to local transition when the objects under study extend much more than the sampling regions, such as in remote sensing. Definition 7. (h-increasingness) Let (τ i , τ i ) be elements of two different p.p. of the same support S i , and {S i , S i ∈ E, i ∈ I} a family of disjoint supports. A finite singular energy ω on the partial partitions D(E) is h-increasing when for every triplet {τ i , τ i , S i ∈ E, i ∈ I} one has, ∀i ∈ I:

ω(τ i ) ≤ ω(τ i ) ⇒ ω( τ i ) ≤ ω( τ i ) (10)
When in addition one has ω(τ i ) < ω(τ i ) for one i at least, and when this leads to ω( τ i ) < ω( τ i ), then the energy ω is strictly h-increasing. For example, a linear energy, i.e. an energy where ω( τ i ) is the sum of the ω(τ i ) is h-increasing, an even strictly h-increasing since

ω(τ i ) < ω(τ i ) for all i ∈ I ⇒ ω( τ i ) < ω( τ i ).
Unlike, the h-increasing energy ω( τ i ) = ω(τ i ) when ω(τ i ) < K and = K when not, is not strictly h-increasing. The energies composed by supremum are also h-increasing, but not strictly.

Finite case When a finite family of partition is under study, then Definition 7 reduces to

ω(τ 1 ) ≤ ω(τ 2 ) ⇒ ω(τ 1 τ 0 ) ≤ ω(τ 2 τ 0 ) (11)
The energies of two partial partitions τ 1 and τ 2 of same support S are compared. If the energy ω is h-increasing and ω(τ 1 ) ≤ ω(τ 2 ), this order is not changed when we concatenate a third p.p. τ 0 of support disjoint from S: Figure 3 shows the geometrical meaning of the h-increasingness.

When, in addition, ω is singular, then ω(π 1 (S)) = ω(π 2 (S)), and also ω[π 1 (S) π 0 ] = ω[π 2 (S) π 0 ], so that Rel. [START_REF] Everett | Generalized lagrange multiplier method for solving problems of optimum allocation of resources[END_REF] can be written in the reverse sense, i.e. by inverting the indexes 1 and 2:

ω[π 1 (S) π 0 ] ≤ ω[π 2 (S) π 0 ] ⇒ ω(π 1 (S)) ≤ ω(π 2 (S)) (12)
h-increasingness permits also to concatenate the supports of the partial partitions. Consider two partitions π 1 and π 2 and two disjoint supports S, S which satisfy the h-increasingness implication [START_REF] Everett | Generalized lagrange multiplier method for solving problems of optimum allocation of resources[END_REF]. We have

ω(π 1 (S)) ≤ ω(π 2 (S)) ⇒ ω(π 1 (S) π 1 (S )) ≤ ω(π 2 (S) π 1 (S )) (13) ω(π 1 (S )) ≤ ω(π 2 (S )) ⇒ ω(π 1 (S ) π 2 (S)) ≤ ω(π 2 (S ) π 2 (S)) hence ω(π 1 (S ∪ S )) ≤ ω(π 2 (S ∪ S )). ( 14
)
Generating h-increasing energies Any weighted sum of h-increasing energies is still hincreasing (they form a vector space). An easy way to generate basic energies in this vector space consists in providing the classes with an arbitrary energy, and to define the energy of the p.p. by composition of their classes. We already saw two laws of composition, by addition and by supremum. Both laws are indeed particular cases of the classical Minkowski expression

ω(π(S)) = u∈[1,q] ω(T u ) α 1 α (15)
which is a norm in R n for α > 0. Even though over partial partitions D(E), it is no longer a norm, it yields strictly h-increasing energies for all α ∈] -∞, +∞[: Proposition 8. Let E ∈ P(E), let ω : P (E) → R be a positive or negative energy defined on P(E). Then the extension of ω to the partial partitions D(E) by means of Relation ( 15) is strictly h-increasing.

Proof. Let π(S) and π (S) be two p.p. of support S, with q, q elements each, respectively. When 0 ≤ α < ∞, the mapping y = x α on R + is strictly increasing and, according to Relation (15), the inequality ω(π(S)) < ω(π (S)) implies

q 1 [ω(T u )] α ≤ q 1 [ω(T u )] α ⇒ q 1 [ω(T u )] α + ω(π 0 ) ≤ q 1 [ω(T u )] α + ω(π 0 ) (16)
hence ω(π 1 π 0 ) < ω(π 2 π 0 ). When -∞ < α ≤ 0, the sense of the inequality changes on both sides of implication in ( 16) but changes again when taking the (.) α . This again lead to ω(π 1 π 0 ) < ω(π 2 π 0 ), and achieves the proof. .. One can easily check that the proposition remains true when ω : P (E) → R -is a negative energy. For α = +∞ (resp.-∞) Minkowski expression yields the supremum (resp. the infimum), which is h-increasing, but not strictly. A number of other laws are compatible with h-increasingness, such as alternating compositions, etc. [ [START_REF] Valero | Hyperspectral image representation and Processing with Binary Partition Trees[END_REF], Veganzones [START_REF] Veganzones | Hyperspectral image segmentation using a new spectral unmixing-based binarypartition tree representation[END_REF], Soille [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] , which all provide h-increasing energies. .

Energetic ordering and energetic lattice for braids 7.1 Climbing energies

The energies on partial partitions which allow minimizations by dynamic programing cannot be totally arbitrary. They must satisfy the axioms of h-increasingness that we just saw, and also of singularity [28] [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF]. Indeed, if some fathers in a braid have the same energies as their siblings, multiple optimal cuts may arise. It is for preventing such occurrences that singularity is introduced.

Definition 9.

Let ω be an energy on the partial partitions D(E), and B be a braid B of monitor hierarchy H. Energy ω is singular when 1. the energy ω({S}) of every class S of H is either strictly smaller, or strictly greater, than the energies of all partial partitions of B of support S:

∀ π(S) ∈ Π(S), ω({S}) < ω(π(S))} or ω({S}) > ω(π(S))}, (17) 2
. if ∀π 1 , π 2 ∈ B and π 1 ∨ π 2 = {S} ∈ Π(E, H), then ω(π 1 ) = ω(π 2 ).
When the braid reduces to a hierarchy, the second axiom becomes useless.

Definition 10. An energy on the partial partitions of E is said to be climbing when it is both h-increasing and singular [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF].

Energetic ordering and energetic lattice

Consider two cuts π 1 , π 2 ∈ Π(B) in a braid B of partitions, and their supremum π 1 ∨ π 2 (see Figure 4). Intuitively, one may assess that, in some sense, π 1 is less energetic than π 2 for an energy

ω when ω[π 1 {S}] ≤ ω[π 2 {S}] in each class S of π 1 ∨ π 2 .

This intuition is true and has the meaning of an ordering relation if and only if the energy ω is climbing:

Theorem 11. Let Π(B) be a braid of partitions of E, and let π 1 , π 2 ∈ Π. Given an energy ω, the partition π 1 is said to be less energetic than π 2 , and one writes π 1 ω π 2 when in each class of π 1 ∨ π 2 the energy of the partial partition of π 1 is smaller or equal to that of π 2: :

π 1 ω π 2 ⇔ {S ∈ π 1 ∨ π 2 ⇒ ω(π 1 {S}) ≤ ω(π 2 {S})} (18)
The relation ω is an ordering relation if and only if the energy ω is climbing.

Proof. "If" part of the proof. The relation ω is obviously reflexive. It is also antisymmetrical, since the double condition π 1 ω π 2 and π 2 ω π 1 means that in each class S of π 1 ∨ π 2 the energies of π 1 (S) and π 2 (S) are the same, which implies by singularity that S is a class of both π 1 and π 2 , hence π 1 = π 2 .

For the concern of transitivity, we consider three partitions π 1 , π 2 , π 3 of the braid B, and the classes S 12 , S 23 , S 31 of the suprema π 1 ∨π 2 , π 2 ∨π 3 , and π 3 ∨π 1 at point x. We have to prove that π 1 ω π 2 and π 2 ω π 3 imply π 1 ω π 3 . According to Proposition 6, there are three possibilities to order the three nested sets S 12 , S 23 , S 31 depending upon the one taken to be the smaller. Take S 12 for example. Then S 23 = S 31 = S is a union of classes of π 1 and of π 2 , hence of π 1 ∨ π 2 . In each of these classes S 12 , S 12 , .. ∈ S the energy of π 1 is ≤ than that of π 2 . These inequalities extend to S by h-increasingness, and we can write ω(π 1 (S)) ≤ ω(π 2 (S)). But we also have by hypothesis ω(π 2 (S)) ≤ ω(π 3 (S)), hence ω(π 1 (S)) ≤ ω(π 3 (S)). As S is an arbitrary class of π 3 ∨ π 1 , we finally obtain π 1 ω π 3 , which proves transitivity when S 12 ⊆ S 23 = S 31 . The two other cases admit similar derivations For the "only if" statement, we must prove that the ordering vanishes either when ω is not singular or when ω is not h-increasing. Consider first an ordering ω whose energy is not singular, and two cuts π and π identical everywhere except in the class S (x), which is replaced by the p.p. τ . Suppose that ω(τ ) = ω(S (x)). This implies π ω π and also π ω π. However we do not have π = π since τ = S (x). Thus singularity is needed. For proving the need of h-increasingness, take for ω the function equal to 1 on each class, plus the linear composition law and a constraint for the singularity. Introduce now the following exception: when the number of classes of a p.p. is 5, then its energy becomes infinite. ω is no longer h-increasing and transitivity is not satisfied, for example at point x in figure 2. This achieves the proof.

The "only if" part of the theorem means that the braids and their cuts have the correct level of generality to lend themselves to a lattice. If one wants to build up energetic orderings on other families of partitions, the energy ω must be more specified. In particular, one can think of braids of order II, where the suprema are cuts of a braid (rather than of a hierarchy), braids of order III, etc.. Coming back to our standard braids, we now prove that the energetic order induces on them a complete lattice.

Theorem 12. Let B be a braid of partitions of E, and ω be an energy on the partial partitions. The set of all cuts of B forms a complete lattice Π(ω, B) for the energetic ordering ω if and only if the energy ω is climbing. Given a family {π j , 1 ≤ j ≤ p} of cuts in Π(ω, B), the infimum ω π j (resp. supremum ω π j ) is obtained by taking the p.p. of lowest energy (resp. highest energy) in each class of the refinement supremum ∨π j .

Proof. If the energy ω is not climbing, there is no energetic ordering, thus no possible lattice. We now suppose that ω is climbing and we treat the finite case in the first place.

A-Finite number of leaves. Let {π i , i ∈ I} be a finite family in Π(ω, B), and π j , π k two members of this family. Define the partition π j ω π k by taking the less energetic of the two p.p. in each class of π j ∨ π k . The partition π j ω π k is a member of the set Π(ω, B), and it is ω -smaller than both π j and π k . Moreover, suppose that another partition π m ∈ Π(ω, B) be Figure 5: a) in case of ∨-composition, there is a unique minimal cut π * and its energy is minimal, but other cuts have also the same energy. b) and c) depict a non h-increasing energy ω(π) which depends on the number of classes of the p.p. π. The two cuts surrounded by ellipses are minimal (hence no energetic lattice), and none of them is obtained by dynamic program, which gives the cut in grey. also ω -smaller than both π j and π k . According to Proposition 6, at point x two of the three classes S jk , S km , and S mj are identical. If S jk = S km = S, then this class S is the support of partial partitions of π j , π k , and π m , and by h-increasingness ω(π m (S) ≤ ω[(π j ω π k )(S)]. For the same reason, we find the same inequality when S km = S mj and when S mj = S jk . Therefore π j ω π k is the largest lower bound of π j and π k .

As the number of leaves of B is finite, the number of partitions π j ω π k with i, k ∈ I is also finite, and their iterated minimizations lead to a partition π 0 ∈ Π(ω, B) smaller than all π i . This π 0 is also the greatest lower bound of the π i since if there exists in Π(ω, B) another π 00 smaller or equal to all π i , then it is also smaller or equal to the iterated (π j ω π k ) ω (π j ω π k ), etc., and finally to π 0 . By duality, the family {π i , i ∈ I} admits a lower upper bound π 1 ∈ Π(ω, B), B-Infinite case Let {S j (x)} be set of all classes at point x of a (possibly infinite) family {π j , j ∈ J ⊆ I} of cuts of B. We saw that these classes form a cone, and that their union S M (x) = ∪S j (x), which belongs to H, has a finite number of leaves. Therefore the number of possible partitions of these leaves is finite, as well as the number of different partitions π j {S M (x). The results of the finite case applies and leads to the local infimum ∧[π j {S M (x)}]. The global infimum is obtained by making x vary. Then, by h-increasingness, the partition ∧π j = {∧[π j {S M (x)}], x ∈ E} is smaller than any other partition (Rel. [START_REF]Diday Spatial Pyramidal Clustering Based on a Tessellation[END_REF]). By duality, we have also ∨π j = {∨[π j {S M (x)}], x ∈ E}, which achieves the proof.

As a consequence, the theorem indicates that dynamic programing no longer works as son as ω is not h-increasing, as depicted in Figure 5 b andc.

The two orderings and ≤

h-increasingness allows us to bridge the gap between the energetic ordering ω for partitions and the numerical ordering of their energies. Consider two cuts π and π of a braid B, and denote by {S i , i ∈ I } the set of all classes of π ∨ π . If τ i and τ i stand for the p.p. of support S i of π and π respectively, and ω for ah-increasing energy, then the left member of (10) means that π ω π and the right one that ω(π) ≤ ω(π ), hence:

π ω π ⇒ ω(π) ≤ ω(π ), (19)
with in particular

π * = ω {π ∈ Π(E, B)} ⇒ ω(π * ) = ∧{ω(π), π ∈ Π(E, B)} (20)
The inverse implication may be false, since several cuts can share the same energy, as demonstrated in figure 5. However in case of a climbing energy, the minimal cut is unique, and it is nothing but the infimum π * of the energetic lattice.

Proposition 13. When energy ω is climbing, when ω(π) is finite for one ω at least, and when the set Π(E, B) is finite, then implication (20) becomes an equivalence.

Proof. As energy ω is climbing, the set Π(E, B) of all cuts of the braid B form a ω-lattice. By uniqueness of the minimum in this energetic lattice, π * ≺ π for π ∈ Π(E, B)\π * . It means that there is a class S of π * ∨ π such that ω(π * {S}) < ω(π {S}). Moreover we draw from the second assumption of the proposition and from Rel. [START_REF] Kiran | Energetic Lattice based optimization[END_REF] that ω(π * ) is finite. As ω is climbing, this gives ω(π * ) < ω(π), and by finiteness ω(π * ) < ∧{ω(π), π ∈ Π(E, B)\π * }. Therefore, if a cut π ∈ Π(E, B) has ω for energy, it can only be π * .

Climbing energies and local knowledge

In earth sciences, most phenomena largely exceed the regions Z in which they are studied. Air-borne and satellites images are of this type. Optimal segmentation of such phenomena must be reached by local, or regional information, and not via a global energy, which would involve the whole space. Here the second axiom of a hierarchy (in definition 3), which states that the number of leaves is finite in any class of the hierarchy, except possibly, in the class {E}, opens the door to a regional approach.

A toy example is given by the following hierarchy of nested partitions of Z where the Take now the case of a satellite image accessible in the window Z, small w.r.t. the surface of the earth. Some previous processing of this image results in a hierarchy H Z with n + 1 levels i (i = 0 for the leaves and i = n for Z) and we want to find its minimal cut according to a h-increasing energy. H Z is the restriction to Z of the hierarchy H of infinite extension which should be obtained if we could access the whole space, i.e. H Z = H {Z}. It is composed by all classes of H included in Z. We admit that the objects of interest are small enough so that every class of the level n -1 can be covered by a convenient Z. The minimal cut π * Z of H Z is computed by the usual dynamic program. As ω is H Z = H {Z}, and as the implication (19 accepts an infinite number of operands, all classes of π * Z different from Z itself are also classes of the minimal cut π * of the whole hierarchy H.

Rebuilding

Theorem 12 shows also that given the finite family {π i , i ∈ I} of partitions, there are two ways for calculating its ω -infimum. If we do not order them, we must take π j ω π k for all pairs π j , π k in the family, but not calculate (((π j ω π k ) ω π l ) ω π m etc., as demonstrated by Figure 6. Alternatively, we can exhibit a sub-hierarchy generated by all classes of the π i and only by them, and minimze it by dynamic programing. We now develop this second solution.

Case of a hierarchy

Consider the family Π J = {π j , 1 ≤ j ≤ J < ∞} of J cuts of an unknown hierarchy H of set of cuts Π. We propose to build up a sub-hierarchy H of H made of all classes of Π J and uniquely with them.

Put π 0 = ∧π j . The classes a, b, etc. of π 0 form the leaves of H , and, as J is finite, each class a, b, etc. of π 0 turns out to be a class of one π j at least.

Define the cones {a k , 1 ≤ k ≤ J} of summits a, b, etc. whose increasing classes are taken in the π j (see figure 7). At each level k the classes a k , b k , etc. form a partition. Indeed, they are nested or disjoint, and they cover the space because each of them contains one leaf at least. Moreover, these partitions increase with k because they classes come from increasing sections of cones. Hence they form a hierarchy, and we can state 1. Let Π J = {π j , 1 ≤ j ≤ J < ∞} be a family of cuts of a hierarchy H, and S J be the set all all classes of the π j . Then there exists a unique hierarchy H with J levels and whose classes are exclusively all elements of S J . Note that it is a purely geometric property of the hiearchies, which does not requires any energy.

Case of a braid

In case of a braid we must construct the smallest partial monitor H whose classes are suprema of the π j . For each leave, e.g. b, when ascending the cone of summit b, we must replace the first two classes which are not nested, e.g. At the end the monitor hierarchy for family {π j } is completely determined (see figure 8) Figure 8: Four cuts π j in an unknown braid of an unkown partial monitor H . The associated cones allow to find the three levels π j of H .

The

  Theory of Braids and Energetic Lattices I -Minimization on Energetic Lattices B.R. Kiran and J.Serra 3, March 2017

Figure 1 :

 1 Figure 1: Dynamic programing works as follows: the energy at any node S is compared to the sum of the energies of the children. If ω(S) ≤ ω(T k ) , T k children of S, one keeps the class S; if not, one replaces S by its sons. The optimal cut is then the union of the remaining classes. It results here in the partition in dotted lines.

  Let π 1 , π 2 , π 3 be three partitions of a braid B. We denote by S 12 , S 23 , S 31 the classes at point x of the suprema π 1 ∨ π 2 , π 2 ∨ π 3 , and π 3 ∨ π 1 respectively. Proposition 6. The three classes S 12 , S 23 , S 31 are nested and the larger two are identical.

Figure 2 :

 2 Figure 2: Three braids and their suprema

Figure 3 :

 3 Figure 3: Hierarchical increasingness

Figure 4 :

 4 Figure 4: The energetic ordering induces a lattice where one takes the less energetic partial partition in each class of π 1 ∨ π 2 (here for a hierarchy).

Figure 6 :

 6 Figure 6: Hierarchy with three levels.The energies of the classes are indicated. Those of the partial partitions are obtained by sums of their classes. the ω of the three partitions is not ( π 2 ω π 3 ) ω π 1

  central class enlarges: i = 0 π 0 = all points of Z i = 1 π 1 = {-∞}...{-3}; {-2}; [-1, +1]; {+2}; {+3}...{+∞}. i = 2 π 2 = {-∞}...{-4}; {-3}; [-2, +2]; {+3}; {+4}...{+∞}. i = 3 π 3 = {-∞}...{-5}; {-4}; [-3, +3]; {+4}; {+5}...{+∞} ............................................... Though |I| = ∞, the number of leaves at any class S i (x), x ∈ Z remains finite as soon as the label i < ∞.

Figure 7 :

 7 Figure 7: Four cuts π j in an unknown hierarchy H . The associated cones allow to find the four levels π j of H .

  b 2 and b 4 , by the class of the supremum π 2 ∨ π 4 which contains b. The algorithm which gives the partial monitor H must determine the children of each class of the {π k }: Consider the infimumπ 0 = ∧{π j }, Determine all cones of summits the classes (or leaves) of π 0 , for each class c in π 0 ; consider the cone at c. For each level k in this cone, if c k ⊆ c k+1 , then keep c k . If c k c k+1 then replace both of them by the class of π k ∨ π k+1 that contains c Continue by going up from all leaves to the root.

They address the two issues of non-constrained and of constrained optimizations. The first one is presented here, and the second further.


Sergio Andrés
email: sergio.ardila9@correo.uis.edu.co

Ardila - Parra

Heller Guillermo

Sánchez Acevedo

Juan José Ródenas
email: jjrodena@mcm.upv.es

Juan José

Sergio Andrés Ardila-Parra

Guillermo Heller

Juan José Sánchez-Acevedo

Ródenas

Damage Assessment of Spinal Bones Due to Prostate Cancer

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