Valentine Roux
email: valentine.roux@mae.u-paris10.fr

Nathalie Aussenac-Gilles

Knowledge Bases and Query Tools for a Better Cumulativity in the Field of Archaeology: The Arkeotek Project

Keywords: knowledge bases, semantic annotation, ontology evolution

Introduction

The Arkeotek Project (www.arkeotek.org) has three complementary and interdependent aims, serving knowledge cumulativity in the field of human sciences [START_REF] Gardin | The Arkeotek project : a european network of knowledge bases in the archaeology of techniques[END_REF]. The first one is to develop methods and tools for constituting "logicist corpuses" made of documents structured in data and interpretation rules, the latter being understood as operations of inferences leading to conclusions or interpretative hypotheses [START_REF] Guilaine | Archaeological Discourse, Conceptual Modelling and Digitalisation: an Interim Report of the Logicist Program[END_REF]. Each rule consists of a proposition (conclusion) and the antecedents (premises) that support it under the form -GIVEN i, THEN p -to be read with the prudence needed for scientific work, "If it is taken as proven that… Then it can be reasonably supposed that…". The second aim is to constitute, based on this model, various corpuses in archaeology of techniques, a field of excellence in Europe. The third aim is to use semantic web technologies and an ontology to make it easy to browse these corpuses and look for specific inference rules. For this purpose, an ontology as well as an automatic annotation tool has been developed [START_REF] Aussenac- | The Arkeotek project: structuring scientific reasoning and documents to manage scientific knowledge[END_REF]. Semantic annotation enables to query the logicist corpuses both on the premises and conclusions of interpretation rules.

These corpuses will have a double function: a function for guiding the researchers in scientific interpretations, and a documentary function for sharing interpretations and facts mobilized by the proposed interpretations. These corpuses should contribute directly to the cumulative process of knowledge as well as to a research dynamics. Furthermore, setting up logicist corpuses in the field of technology should serve as a model for the type of corpus which could be developed in the field of human sciences.

This paper presents the SCD format (section 2) used to represent inference rules as well as the challenge raised by our project (section 3). Then we report the ontology and annotation tool developed for information retrieval in SCD corpuses. We rely on an experiment carried out in the domain of grinding stones (section 5) to report the strengths of this project to manage, to exchange and to discuss scientific findings.

Collecting logicist documents: the Logicist Corpuses Project

Four steps are required to constitute a logicist corpus. First of all a) a significant number of scientific texts concerning the archaeology of techniques have to be transformed into logicist documents, that is documents presenting the scientific construct under the form of an inference tree, linking initial propositions to final propositions through successive intermediate level propositions obtained by an inference process; b) the data connected to these scientific constructs have to be collected; c) these documents have to be translated in English or French (depending on the original language), d) they have to be then published in the SCD format ('Scientific Construct and Data', this format has been developed by the publisher Editions Epistèmes) in The Arkeotek Journal (www.thearkeotekjournal.org).

1.1

The SCD format Briefly, the SCD format edits logicist documents and permits their rapid reading as well as an easy exploration of their constitutive elements -data bases and inferential operations -. Exploration of the constitutive elements is done according to four levels of reading, each level corresponding to a more or less detailed consultation of the scientific construct.

The first level of reading is that of a general outline listing the main blocks of propositions organizing the scientific construct. The second level corresponds to a rapid reading of the different propositions contained in each block, i.e. a rapid consultation of all the propositions that organise a scientific construction: a) the initial propositions which are generally distributed between three blocks: the observational, the comparative and the reference data, b) the interpretative propositions which include the intermediate and the final propositions, the former linking the latter to the initial propositions. The third level of consultation consists in reading: a) the commentaries developed for each proposition and written in natural language, b) the details related to the initial propositions if given and c) the antecedents upon which the interpretative proposition rest. In the latter case, the antecedents are indicated in order to unravel the logico-discursive operations founding the proposition. The fourth level of reading is that of the series of data mobilised in building initial propositions. These data are given under the form of illustrations (tables, graphics, images, videos, pdf). These illustrations accompany initial propositions or details of initial propositions.

Inference rule corpuses as supports for knowledge exchange

The SCD publishing of logicist documents enables: a) a rapid reading of the rules used by the researchers to obtain or support a result ; this is a major point since nowadays there is no automatic tool enabling to extract content of scientific texts and therefore able to propose solutions to the "crisis of scientific information"; b) easily understandable scientific reasoning, and, in return, better sharing of knowledge within the discipline; c) exhaustive access to the databases on which the scientific constructions of a field are based which is a major advantage as compared to the printed publication which constantly have to face inherent problems linked to the restricted space available for research databases -the archaeologists should be especially sensitive to these expectations, in so far as the present publishing process does not allow experimental data to be generally shared even though these data are indispensable to the dynamic of their research -; d) the auto-archiving of research data and a solution for the perpetuation of the indexing of the data.

The SCD publishing of logicist documents enables also the constitution of knowledge bases that collect all available rules. They include the rules from the articles of the journal The Arkeotek Journal and from monographs of the Référentiels collection (www.arkeotek.org). They can also include rules published in other journals or books so long as these rules have been rewritten according to logicist principles (such as the rules published by Gallay in 2007). At the time being, we have a unique rule base including the few hundred inference rules found in the articles and the digests published by The Arkeotek Journal. These rules can be considered as either 'local' or 'universal'. 'Local' rules correspond to ordering operations (classification) or comparative operations (comparing two object collections). They are local in the sense that they apply strictly to the body of data studied in the article (or book). They are expressed under the form KNOWING i, THEN p. The rules with a 'universal' character are those rules which are not specific to the studied body of data. They call generally upon implicit reference data (the 'common sense'). Their validity can be assessed in terms of transferability. For this purpose, they have to be generalised and formulated under the form IF … THEN ... In The Arkeotek Journal, the inference rules contained in each article ('local' and 'universal' ones) are listed per article in the tab CORPUSES/ RULE BASES. The inference rules with a 'universal' character are given a specific access in the menu of the SCD article in the tab 'rules of inference'. These rules are put to debate through a forum. The Arkeotek editorial board makes a first comment by generalising the rules under the form IF … THEN. The scope is to assess their validity through a formulation enabling their application in various chrono-cultural situations.

In archaeology, cumulative process of knowledge involves mainly propositions obtained through 'local' inference rules, which are mainly descriptive. Propositions obtained thanks to 'universal' inference rules are discussed but rarely subject to empirical verification. Therefore they are not taken up in the cumulative process of knowledge.

Queries on inference rules: the DYNAMO project

Motivation for querying rule corpuses

Making logicist documents available on the web enables an easy access to these information resources. People can access to the data and the rules of inferences, debate their validity and compare the rules from one corpus to the other. Knowledge and techniques from the Semantic Web community can contribute towards the realization of cross-corpus access [START_REF] Hollink | Semantic Web Opportunities for Digital Libraries[END_REF]. The Arkeotek project data set is particularly suitable for the Semantic Web approach, since rule corpuses form rich and well-structured knowledge sources. Moreover, existing controlled vocabularies and thesauri can be used to index large collections of text or inference rules in our case. The Arkeotek Journal web site can be considered as a portal where semantic search is required to get precise information. Semantic annotation enriches rules with a formal representation of their content in the form of concept lists or conceptual graphs. This annotation requires to define adequate domain ontology, and to match the terms used to label concepts with the language used in the rules of inference.

Questioning the rule base implies questions both on 'local' and 'universal' inference rules, bearing either on their premises or on their conclusions. Two sorts of questions are considered, general and particular. General questions call upon inference rules as a guide for interpretation. Questions may be "Given i attributes, what can I say?" or "What attributes do I need for founding interpretation j". Particular questions call upon inference rules as a source of documentation along with the critical apparatus. Questions are for example "What are the characteristics of i material?" "How was organised the production of i material?"

In any case, answers are inference rules, the premises and/or conclusions of which match the request. The user can then consult archaeological interpretations on specific subjects, but also the foundations of the archaeological interpretations, including data bases.

Cross consultation of corpuses make it possible to contrast and compare rules defined in various sub domains of archaeotechnology.

An Ontology for Semantic Annotation: principles

The ontology covers the domain of the Archaeology of Techniques, with a rich lexical component so that concepts can be used to index text: a sentence will be indexed with all the concepts which have a linguistic realization in this sentence. In this regard, it is a lightweight model with a terminological component: we call it a termino-conceptual resource. The ontology content, its design principles and its structure are influenced by its use for textual annotation. The ontology design principles are the following (AUSSENAC-GILLES, 2006):

-Its scope covers the domain determined by the set of rules to be annotated but only those. Concepts are distributed between the ones related to the description of objects (intrinsic and extrinsic attributes), and the ones related to their interpretation.

-Concepts and terms are those required to adjust requests and rules. The model intends to reflect the conceptual categories that can be differentiated through the use of language.

-The ontology has been made "a minima", with few properties and no formal axiom, but with a rich and extended set of terms labelling each concept. The ontologist makes it evolve when rules from a new specialized technical domain are added to the collection. The ontology data-model makes explicit the concept lexicalizations using a term structure and a denotation relation from terms towards concepts [START_REF] Reymonet | Ontology Based Information Retrieval: an application to automotive diagnosis[END_REF]. At the time being, the ontology gathers concepts and terms to express technical interpretations made by archaeologists as well as those required to describe objects (extrinsic and intrinsic properties) in the domains of ceramics, lithic industries and beads. It contains 372 terms labeling about 82 concept classes with 5 properties.

Each semantic annotation of a rule can be represented as an OWL graph of term and concept instances, with semantic relations linking concept instances. The annotation process relies on mapping terms in the ontology with the words used in the rule premises or conclusion. This mapping relies on a measure that allows small spelling variations to map nouns, adjectives and verbs whatever their gender, number or conjugation when they are used in the sentence to be annotated. When setting the software parameters, the ontologist has to decide whether to take into account semantic relations or not, and which ones. Based on the concepts identified in each proposition, the system exploits the semantic relations connecting these concepts in the ontology to connect the instances in the annotation graph. In the particular case of the Arkeotek corpus, annotations do not include semantics relations between concepts. To sum up, the annotation algorithm automatically generates an OWL graph for each proposition, and the ontologist or corpus editor checks, improves or modifies it before he validates this representation.

Ontology and annotation tool

Querying the rule base implies first to develop a relevant ontology, then to annotate each rule, and then to express and match queries. The tools and infrastructure for all these tasks have been defined within the DynamO project (http://www.irit.fr/dynamo/). The originality of this project is to define a unique environment (TextViz, a plug-in of the Protégé ontology editor (http://protege.stanford.edu) for ontology management and use for semantic annotation, in order to anticipate ontology evolution consequent to the corpus evolution and changes in uses needs. As long as new inference rules are added to a corpus, the ontology is adapted by adding new terms or concepts, or more deeply modified, so that new rules could be precisely indexed. The Dynamo project experiments an extension of the notion of ontology, a termino-ontological resource that enriches an ontology with terms denoting each concept [START_REF] Reymonet | Ontology Based Information Retrieval: an application to automotive diagnosis[END_REF]. Terms play the role of linguistic markers to identify that concepts are mentioned in rule propositions.

Another original feature of the Dynamo project is to provide support for ontology evolution in the TextViz system: the ontology is modified every time new terms or concepts are required for rule annotation. The Dynamo project decided to test and compare two different and complementary approaches for ontology evolution: (1) a supervised evolution process based on the ontologist's initiative [START_REF] Reymonet | Ontology Based Information Retrieval: an application to automotive diagnosis[END_REF] -the ontologist can manually select a phrase in a sentence and define it as a term or as a concept label connected to this term; (2) an adaptive multiagent system that makes evolution suggestions on the basis of the terms and semantic relations extracted from the corpus with NLP tools [START_REF] Sellami | Dynamic ontology coconstruction based on adaptive multi-agent technology[END_REF].

With TextViz, the evolution cycle is a loop where the evaluation of quality criteria (like a list of concepts that have to be identified in each annotation) may lead to modify the ontology, and where changes in the ontology may lead to launch a new annotation process. The interface displays all the resources and information required to support this cycle: the hierarchy of concepts with, for each of them, the terms that denote them; the current quality of the annotations of the rule corpus and their validity; three views on how a selected rule is annotated with concepts: a graphic view, a list of concepts and a textual view where tagged phrases are high-lighted with colors.

The search and editorial tools

Querying the rule base also requires a set of tools for the end-user, including an adequate browsing and querying interface. Graph-based semantic annotation makes it possible to express simple queries and match them with appropriate documents [START_REF] Hildebrand | Interactive Exploration of Heterogeneous Cultural Heritage Collections[END_REF]. This author promotes the combination of various vocabularies to guide the formulation of queries with precise words. The Arkeotek overall interface should make it possible to browse the rule collection paper by paper or within a given sub-domain, or to query the rule corpus with natural language requests. The ontology can also be use as a support to express requests and to browse the rule collection.

The rule and data reading interface will comprise a) a natural language query device, b) an ontology browsing device that helps build request with concepts, c) a rule reading device to browse any request answers. Browsing the rules returned as answers makes it possible to compare or contrast these rules. It offers an innovative reading of the different rules with one or several corpuses, and the possibility to consult their premises and conclusion. Thereby, the reader can check the strength and validity of the available rules and data by consulting back the original publications.

Experiment: Testing the "grinding material" corpus

The Arkeotek Journal has published three articles and one digest on grinding material (different bodies of data, different chrono-cultural periods and area). This thematic corpus is made up of 83 inference rules. Out of these 83 inference rules, 14 rules can be reformulated as so-called 'universal' rules in the forum.

The corpus has been presented and discussed within a workshop which gathered domain experts (http://www.arkeotek.org/index.php?option=com_content&task =blogcategory&id=31&Itemid=43). Two categories of questions have been raised, technical and theoretical. On the technical side, the Arkeotek Project has been acknowledged positively: the logicist documents and the search tools proved to be very efficient for documentary purpose (rules and data) as well as for comparing inference rules. For example, queries have been formulated about standardised grinding material: "what can I say if I have standardised grinding tools?" The returned rules of inference, proposed by two authors using different terminologies, propose that standardized grinding tools could be interpreted as efficient tools. By comparing the rules of inference, it appeared a) that terminology and theoretical framework can be different but the rules of inference very much comparable, b) that rules of inference can be very current in one field but however not well founded; indeed, discussions highlighted the fact that standardized tools do not express efficiency but specialisation of the manufacturers. In other words, the query tool enabled us to highlight the fact that most of our interpretative rules are implicit and therefore not really discussed, therefore preventing from a proper cumul of knowledge. On the theoretical side, the Arkeotek project has been perceived as a project which should impact on our researches: the logicist documents show that most of our constructs are made up of "middle range" propositions, as well as of quite useless propositions (a significant number are in fact redundant); the ones calling upon 'universal' rules appear, on the contrary, the most interesting ones since they enable us to obtain "high level" interpretations. Nevertheless the assessment of their foundations needs more experiments. In this regard their formulation under the form of rules opens paths to new researches.

Conclusion

In conclusion, the Arkeotek Project is definitely acknowledged as efficient in terms of extracting knowledge from linear texts, providing formatted documents enabling the development of searching tools, and offering a library of scientific inference rules along data and a solid critic apparatus (since the premises of each conclusion are explicit). In this regard the Arkeotek Project provides the means for a better research dynamics. By extending its network among the scientific community, it should be slowly appropriated by researchers in Human Sciences as a powerful technical and epistemological tool for constructing and disseminating scientific results.

The Arkeotek project illustrates the importance of structured documents for developing tools which enable us not only documentary search, but also scientific search. The current experiment in the domain of grinding material and the use of the TextViz tool confirmed the gain brought by semantic web technologies. This tool is also experimented in two other domains like car electronic-fault diagnosis and repair or software maintenance. To be relevant, the TextViz must offer good evolution capabilities that will keep the termino-ontological resource up-to-date with regards to the corpus and the domain knowledge.

Figure 1 :

 1 Figure 1: Example of publication of a paper into SCD format in The Arkeotek Journal.

Figure 1 :

 1 Figure 1: The Arkeotek ontology high-level concepts.

Figure 2 :

 2 Figure 2: Proposition annotation with TextViz. On the left top, an inference rule made up of premises and a conclusion.Just below it, a graphic view of its annotation. In the middle, top: the ontology concept hierarchy, bottom: terms labelling the "outillage_macrolithique" concept. On the right, top: annotating concepts of the rule indicated with colour, bottom: inference rules sorted according to their validation score.


Luc Libralesso
email: luc.libralesso@grenoble-inp.fr

Vincent Jost

Khadija Hadj Salem

Florian Fontan

Frédéric Maffray

Triangle width: at the intersection of graph theory, scheduling and matrix visualization

Keywords: Combinatorial Optimization, Scheduling, Graph theory, Binary matrix visualization

We introduce a new problem that can be studied from 3 different angles: scheduling, matrix visualization and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to prove several of its NP-Hard and polynomial subcases. This problem allows to find more elegant (and arguably shorter) proofs for several combinatorial problems. Including "Can a matrix can be made triangular by permuting rows and columns?" and weak k-visit. It also provides an elegant generalization of Johnson's argument for the two-machine flowshop.

Introduction

In many agendas, one has to first make (costly) investments before being able to carry (rewarding) projects. Each project requires a specific set of investments, while each investment might be needed in several projects. Usually researchers allow to select only a subset of projects to be completed (see [Lus82]). However, we show in this paper that considering the constraint of selecting all projects leads to an elegant problem with real world applications. The question we tackle can be stated as follows: "In which order should we schedule our (predefined sets of) investments and projects, so as to minimize the initial treasury (or loan) required to achieve our agenda?" More conceptually, each project has some required investments that should be paid. Possibly, projects have investments in common. Depending on the investment/project schedule, the initial required treasury varies. We note that it is not allowed to reach a negative amount of treasury. Figure 1 shows an example of possible order of projects. All investments (resp. projects) cost (resp. produce) 1 unit of money except investments 5 and 6 which cost 3 units, and project f produces 2 units.

For more details:

project a requires investments 1,2

project b requires 2,3 project c requires 3,4 project d requires 4,5 project e requires 5 project f requires 2,4,6

In this example, we choose to carry out project a first. Since it requires investments 1 and 2 that both cost 1 units of money, globally, project a costs 2 units of money and produces 1 unit of money. Then, we schedule other projects until every project is completed. Using this specific schedule, we need at least 7 units of treasury to complete this specific project schedule. We now give some examples of applications in which the problem described above arises.

In parallel database join optimization [MR93], one processor loads pages of the secondary memory and executes joins when they are available. We can represent this problem as a hypergraph where vertices are pages and edges are joins to perform. We want to get a page and join load order that minimizes the total execution time.

This problem also occurs for image processing in embedded vision systems (for more details see [HSKM16] and [HSKM18]). These systems consist of calculating a series of image transformations (output tasks). All these transformations require some parts of the original image (input tasks).

Finally, it is also interesting from a theoretical point of view. Although the results can be applied in various fields (scheduling, graph theory and data visualization), the problem is not well studied. It generalizes the following problem, whose computational complexity was asked by Wilf [Wil93]: "Given a square 0/1 matrix, is it possible to make it triangular by permuting both rows and columns?". Wilf's problem was proved N P-Hard [FRV15], but the proof is very far from straightforward. We show that the triangular matrix problem is a subcase of triangle width and give a simple N P-Hardness proof.

The structure of the paper is the following. In Section 2, we present three different formulations of triangle width (vertex ordering, scheduling and matrix visualization). We show the equivalence between these formulations. In Section 3, we prove the N P-Hardness of the problem and of some of its sub-cases. In Section 4, we study polynomial time cases of triangle width, in particular, we give an optimal greedy algorithm that solves a generalization of F 2||C max with negative time-lags which is inspired by Johnson's algorithm [GJS76].

Definition and Representation

Let V be the set of investments, and E be the set of projects. We express the dependence of a project e ∈ E on an investment v ∈ V by an hypergraph H = (V, E) in which the vertex v is incident to the hyper-edge e.

The cost of each investment v is given by the function p v : V → R + . Similarly, the revenue of each project e is given by the function p e : E → R + .

Consider the sequences σ V (order of investments) and σ E (order of projects).

For a finite set S, we denote by perm(S), the set of permutations on S.

Input:

-

hypergraph H = (V, E) -p v : V → R + cost of vertex v (investment)
p e : E → R + production of hyper-edge e (project) b ∈ R + amount of initial treasury

Question:

Is there a permutation σ ∈ perm(V ∪ E) such that:

for all e ∈ E and for all v ∈ e, σ(v) < σ(e) for all prefix R of σ, b

+ x∈R p(x) ≥ 0 where p(x) = -p v (x) if x ∈ V and p(x) = p e (x) if x ∈ E.
As a first result, we observe that given a permutation σ V of vertices (investments), it is possible to find an optimal permutation σ E of projects by scheduling them as soon as possible.

Theorem 1 For any hypergraph H = (V, E), any cost function p : V → R + , any profit function p : E → R + and any permutation σ V ∈ perm(V ), an optimal permutation σ E (depending on σ V ) can be found greedily by scheduling elements of E as soon as possible.

Proof. We use an exchange argument.

Assume there is a solution given by permutations σ V , σ E in which a project e which is not scheduled as soon as possible. Scheduling it just after its last required investment will maintain feasibility and will not increase the amount of initial treasury required.

Considering Theorem 1 results and the solution given in the introduction, we can obtain a new optimal permutation of projects (σ E ) with respect of a given permutation of investments (σ V ). We obtain the schedule described in Figure 2. We obtain the permutation σ E =< a, b, c, d, e, f > and it leads to a required treasury of 5 which is better than the solution given in the introduction which was 7. We now present in this section 3 new formulations of this problem using Theorem 1 (i.e. vertex ordering, scheduling and binary matrix visualization).

Formalization and formulation as a vertex ordering problem

Using Theorem 1, we can deduce the following decision model for our problem and express a solution using only a permutation on vertices σ V (if there is no ambiguity, we call it σ)

Input:

-

hypergraph H = (V, E) -p v : V → R + cost of vertex v (investment) -p e : E → R + production of hyper-edge e (project) -b ∈ R + amount of initial treasury Question:
Is there a permutation σ on vertices (investments) such that after each investment, just before starting a project (if one is available), the treasury is positive. More formally, at each step i ∈ {1, 2, . . . , |V |} (gathering the funds to start the i th investment), the amount of initial treasury (b) together with the amount of money produced by already carried projects (which is e∈Eσ(i-1) p e (e) where E σ (i -1) denotes the set of hyper-edges induced by the first i -1 vertices of the permutation) must be at least the cost of the first i investments (

i j=1 p v (σ(j)))
In other words, the permutation σ must satisfy Inequalities (1). 1) Figure 3 presents an example of a vertex ordering. All vertices cost 1 unit of treasury except the two rightmost ones that cost 3 units of treasury. Each hyperedge (project) produces 1 unit of treasury except the hyper-edge of degree 3 that produces 2 units of treasury. We start with an initial treasury b of 5. As will be presented in the next section, the vertex ordering formulation is very helpful to obtain complexity results. Indeed, N P-Hardness proofs are tedious to make with other formulations.

∃ σ ∈ perm(V ), ∀i ∈ {1, 2, . . . , |V |} , b + e∈Eσ(i-1) p e (e) ≥ i j=1 p v (σ(j)) (
(a) i = 1, funds: 5 -1 = 4 (b) i = 2, funds: 4 -1 = 3 (c) i = 3, funds: 3-1+1 = 3 (d) i = 4, funds: 3-1+1 = 3(e) i = 5, funds: 3-3+1 = 1(f) i = 6, funds: 1 -3 + 2 = 0

Formulation as a scheduling problem

Let us consider the following two-machine scheduling problem:

Input:

hypergraph H = (V, E) p v : V → R + durations of tasks on the input processor.

p e : E → R + durations of tasks on the output processor.

b ∈ R + amount of allowed idle time on the output processor.

The hypergraph H defines the requirements between input and output tasks.

An edge e (output task) has all its endpoints in H as requirements.

Each task of V (resp. E) has duration p v (resp p e ). The goal is to find a schedule defined by permutations σ V , σ E such that tasks V (resp. E) are scheduled in these orders on the input processor (resp. output processor) with idle time of b on the output processor. In our context, there is no sense of having an input task which does not have any related output (in this case, we can just remove it). Also, if we have output tasks without any prerequisites, it is dominant to place them at the beginning of the scheduling on the output processor and we do not need to consider them in our problem. Thus, up to preprocessing, we assume that there are neither isolated vertices nor empty edges in the input.

As for the vertex ordering problem, one can note that the order of output tasks (hyper-edges) is strongly related to the order of input tasks (vertices). Indeed, when scheduling an input task v, it is dominant to schedule all output tasks e that have all their precedences scheduled (i.e. if there is a feasible solution that do not respect this property, one can exchange output tasks to make this property true without removing feasibility). This argument allows us to have a more compact formulation and only consider the set of permutations σ

V instead of σ V × σ E .
More formally, for each step i of a feasible schedule (scheduling the i th input task), one has to guarantee that the sum of the (i -1) th output task processing times ( e∈Eσ(i-1) p e (e), where E σ (i-1) is the set of output tasks induced by the first i -1 input tasks of the permutation) and the allowed idle time b is at least the sum of the precedences of the i th output tasks ( i j=1 p v (σ(j)). Otherwise, it implies idle time larger than b.

In other words, one has to satisfy the Inequalities (2).

∃ σ ∈ perm(V ), ∀i ∈ {1, 2, . . . , |V |} , b + e∈Eσ(i-1) p e (e) ≥ i j=1 p v (σ(j)) (2)
Figure 4 presents an example of feasible schedule. There are 6 tasks on the input processor and 6 tasks on the output processor. Tasks on the output processor have one or more dependencies represented with arrows. We now show that satisfying (2) is equivalent to have a feasible schedule.

Theorem 2 Let σ be a permutation of tasks. σ satisfies (2) if and only if the schedule defined by σ is feasible. 2) are not verified, we prove by contradiction that it is not possible to compute a feasible schedule with idle time b on the output processor. Consider a feasible schedule such that the output permutation σ V does not respect inequalities (2) for a position i. We have b + e∈Eσ(i-1) p e (e) < i j=1 p v (σ(j)). When scheduling the vertex at position i, there is an idle time b ≤ b. Since the schedule is feasible, we have b + e∈Eσ(i-1) p e (e) ≥ i j=1 p v (σ(j)). Thus, it implies that b+ e∈Eσ(i-1) p e (e) ≥ i j=1 p v (σ(j)). Contradiction.

Formulation as a binary matrix visualization problem

Let us consider the following problem:

Consider a binary matrix with rows (resp. columns) of a given height (resp. width). Consider a line parallel to the diagonal by an offset b called the limit (see Figure 5). Is it possible to find a permutation of rows (resp. columns) of the matrix such that each black tile of the matrix is below the limit?

More formally, we can describe the problem as follows:

Input:

-hypergraph H = (V, E) -p v : V → R + width of column v -p e : E → R + height of row e -b ∈ R + offset of the limit Question:
Is there a permutation of columns (resp. rows) σ V (resp. σ E ) such that every black tile is below the limit (i.e. line parallel to the diagonal).

As in the scheduling version of triangle width, we can notice that the permutation σ E can be determined once σ V is given.

We then want to find a permutation of columns σ V such for every column, all its black tiles lie below the limit. The limit can be defined by the set of points given in equations (3).

limit = {(b + i, i) | i ∈ [0; e∈E p e (e)]} (3)
Since all black tiles in the matrix are composed of rectangles, one can simply check if the upper-right corners are above the limit. Each row at position i must have the sum of the offset (b) and its height ( e∈Eσ(i-1) p e (e) where E σ (i -1) is the set of columns with at least one black tile in common with at least one of the first i -1 input tasks of the permutation) at least its width ( i j=1 p v (σ(j))). Doing so, our binary visualization problem can be formulated as in equations (4). 4) Figure 5 presents an example of matrix visualization. The objective is to find a permutation on rows/columns such that all black tiles lie below the limit represented by the dashed red line.

∃ σ ∈ perm(V ), ∀i ∈ {1, 2, . . . , |V |} , b + e∈Eσ(i-1) p e (e) ≥ i j=1 p v (σ(j)) (

Wrapping up formulations

Theorem 3 (formulation equivalence) The three triangle width formulations: vertex ordering, scheduling and matrix visualization, are equivalent problems.

Proof. Since all formulations given by ( 1), ( 2) and ( 4) are strictly equivalent, an optimal solution for one is optimal for the others.

We now discuss the strengths and weaknesses of the 3 proposed formulations:

The vertex ordering formulation is very convenient to obtain complexity results.

As we show in the next section, we use this formulation to obtain N P-Hardness proofs.

The scheduling formulation is usually found in applied and industrial problems. However, this formulation makes complexity results difficult to obtain.

During experiments on triangle width, we noticed that instances and solutions were easier to visualize using the matrix form. Indeed, the scheduling version represents hypergraphs as a bipartite graph where the vertices are on one side, the hyper-edges on the other and there is a link between a vertex and hyper-edge if one contains the other. The vertex ordering uses Venn diagrams to represent hypergraphs. Both fail to visualize hypergraphs of reasonable size (i.e. more than 10 vertices and edges). We believe that the matrix visualization form allows to provide valuable information. Along with the results presented in this paper, we provide an interactive web visualization of triangle width instances where one can try to solve instances of triangle width at the following url: http: //librallu.gitlab.io/hypergraph-viz/.

This paper advocates that each formulation has its strengths and weaknesses. While working on a specific formulation, some results may appear difficult to obtain. Switching to another representation often helps to get elegant and concise arguments. At the beginning of our work on triangle width, we only considered the scheduling version. The N P-Hardness proof was very difficult to obtain. As soon as we changed to the vertex ordering representation, results were much easier to obtain. In order to fully understand the benefit of switching formulations, we invite the reader to think of a N P-Hardness proof for the scheduling formulation without using the vertex ordering formulation.

In the next sections, we consider several sub-problems or related problems, and obtain more elegant results by switching representations.

N P-Hard cases

3.1 p v = a, p e = 1, H is a graph, 1 ≤ a ≤ |V | is N P-Hard
Consider the vertex ordering formulation. We want to find an order σ on the vertices such that:

b + |E σ (i -1)| ≥ a • i ∀i ∈ {1, . . . , |V |}
Where b ∈ {1, . . . , |V |}. This problem remains N P-Hard even with p v = a, p e = 1 and if H is a graph.

Theorem 4 triangle width is N P-Hard even with p v = a, p e = 1 and H is a graph.

Proof. Reduction from Clique, which is defined as follows: Given a graph G = (V, E) and an integer k, is there a set of k vertices pairwise adjacent? Clique is a well known N P-Hard problem [GJ02].

Consider a graph G = (V, E) and an integer 0 ≤ k ≤ |V |.

We construct the graph G = (V , E ) as follows :

-V = V ∪ {j 1 , j 2 , . . . j k } -E = E ∪ {(g, j) | g ∈ G, j ∈ J} -a = k -b = k(k+3) 2
An example of such a graph G is described in Figure 6.

G J

Fig. 6: We consider a new set J of k vertices which are linked to all vertices in G. In this example, we search for a clique of size 3

First, we observe that finding a clique of size k in G is equivalent to find a clique of size k + 1 in G . Next, we show that it is also equivalent to the existence of a feasible solution for the vertex ordering in G .

there exists a feasible solution for triangle width =⇒ there exists a clique of size k + 1 in G : For i = k + 2, we obtain for all i ∈ {1, 2, . . . ,

|V |}, b + |E σ (i -1)| ≥ a • i. It implies that k(k+3) 2 + |E σ (i -1)| ≥ k • (k + 2) =⇒ |E σ (i -1)| ≥ k(k+1)

2

. The only possibility for this inequality to be satisfied is that G contains a clique of size k + 1.

clique of size k + 1 in G =⇒ a feasible solution for triangle width: As the previous case, consider the step i = k + 2. Since there exists a clique of size k + 1 in G , we can satisfy steps i = 1, 2, . . . , k + 1. Then, we can add the remaining vertices in J which contributes each by k. And finally, the remaining vertices of G which will also contribute k. Thus, a clique of size k + 1 in G implies a feasible solution for triangle width.

p

v = 1, p e = 1, H hypergraph is N P-Hard
Theorem 5 triangle width is N P-Hard, even when p v = 1, p e = 1 and H is a hypergraph.

Proof. We perform a reduction from the version with p v = a, p e = 1, H a graph, 1 ≤ a ≤ |V |.

We construct the following instance with p e = 1, p v = 1 as follows:

-V = {v u,i | ∀u ∈ V, ∀i ∈ {1, 2, . . . , k}} -E = {{v u,i | ∀u ∈ e, ∀i ∈ {1, 2, . . . , k}} | ∀e ∈ E}
The idea is to divide each input task to a separate tasks which belong to the same hyper-edges. It is dominant to schedule the new input tasks by block. Since a < |V | the reduction is polynomial. Thus, solving the sub-case p v = 1 is N P-Hard.

Figure 7 shows an example of column duplication. If we are able to solve the case where columns and rows have the same size, we are also able to solve the case where a column is two times bigger than a row.

Link with weak-k visit

We now study a related vertex ordering problem described in the literature and show that it is a sub-case of triangle width. Weak-k visit was originally described in [AFN00] and is known to be N P-Hard. It consists of visiting a graph, starting with k "free" vertices (in the process getting some initial treasury. Again, consecutive vertices are not required to be adjacent). Then, each of the n -k other vertices costs k. The goal is to find a permutation of vertices such that the treasury is always positive. More formally, the problem can be described as follows:

Input: A graph G = (V, E), an integer 0 ≤ k ≤ n.
Output: A permutation of vertices σ : V → {1, . . . , n} such that:

|E σ (i)| ≥ k(i -k) k + 1 ≤ i ≤ n (5)
Where E σ (i) is the set of edges induced by the first i vertices of the permutation.

We now show that weak k-visit is a sub-problem of triangle width. First, we can notice that, if |E| < k(n-k), the graph is not weak-k visitable since the equation ( 5) for i = n would not be respected. We can safely assume that |E| ≥ k(n -k). Thus, one can only consider the equations for k + 1 ≤ i ≤ n -1.

We can reformulate the triangle width as follows and specialize it with edge weights equal to 1 and vertex weights equal to some constant a. We obtain:

|E i-1 (σ)| = a • i -b 1 ≤ i ≤ n
By using the variable j = i -1, we obtain:

|E j (σ)| = a(j + 1) -b 0 ≤ j ≤ n -1 Since |E i (σ)| ≥ 0 and k ≥ 0, we can deduce the definition of weak-k visit. |E σ (i)| ≥ k(i -k) 0 ≤ i ≤ n -1
Finally, by fixing j = i, a = k, b = k 2 + k one can see that triangle width generalizes weak-k visit problem.

We note that this result also constitutes a new N P-Hardness proof for weak-k visit.

3.4 Can a matrix can be made triangular by permuting rows and columns?

[FRV15] proves that finding if a matrix is triangular if we permute its rows and columns is N P-Hard. We give a new (arguably much simpler) proof by reducing the problem to triangle width, p v = 1, p e = 1, H hypergraph (see section 3.2). Consider a matrix M and an offset b. We construct a matrix M where we add b rows made of zeros to M . Then one filled column (C 0 ) with all ones (See Figure 8. In our matrix representations, zeros are white tiles and ones black tiles). The existence of a permutation making M triangular is equivalent with finding a permutation making M triangular below b. Indeed, it is dominant to start with column C 0 in our scheduling and the rows with only one 1 in C 0 first. Putting C 0 first, will allow exactly an advance of b for the matrix M . Thus, answering if a matrix can be made triangular by permutations can solve the decision problem of triangle width. We define a connected ordering as follows. Consider a hypergraph H = (V, E).

A connected ordering orders connected components by block (i.e. if two vertices i, j belong to the same connected component, there is no vertex k belonging to another component between i and j in the connected ordering) of decreasing densities (|E| -|V |). Within each connected component, for all prefixes S ⊆ V , the following vertex belongs to an edge with the maximum number of vertices in S.

One can obtain a connected ordering by executing the steps described by the Algorithm 1.

We now use connected orderings to present some polynomial cases when the processing times of vertices is small. Indeed, with relatively small a, an order exploring the first neighbours of already explored vertices is guaranteed to be optimal (we call this kind of ordering, Prim-like orderings). We present results when H is a hypergraph of fixed edge size (and in particular when H is a graph).

Theorem 6 If H = (V, E) is a k-uniform hypergraph ( i.e. |e| = k ∀e ∈ E) and a ≤ 1 k-1
, then there exists a polynomial time algorithm to solve triangle width.

Proof. The polynomial time algorithm starts by finding a connected ordering as explained above. We claim that the resulting solution is optimal. Indeed, using a connected ordering, except for the first hyper-edge we select, each hyper-edge has a vertex already selected and will cost at most a • (k -1) ≤ k-1 k-1 = 1. This property guarantees that we can add it without decreasing the objective value. amount of work. Tasks to the right of this line produce more work on machine 1 than on machine 2 (tasks a and d in Figure 9). This implies some idle time on machine 1. The computation time and the idle time on machine 1 give us a lower bound for the minimal C max and the solution of triangle width gives us a feasible solution. Thus, maximizing triangle width on this instance is equivalent to minimizing F 2||C max . Figure 9 illustrates this argument.

We provide now Johnson's exchange argument using triangle width visualization (presented on Figure 10). Given two tasks i and j, we can compute the corresponding objective modification by:

min(P j1 , P i2 ) if i is scheduled before j; min(P i1 , P j2 ) if j is scheduled before i Task i is before task j in the optimal schedule implies that min(P j1 , P i2 ) ≥ min(P i1 , P j2 ) which gives us Johnson's rule ([Pin16]).

F 2|t

j ∈ [-min(p 1j , p 2j ), 0]|C max
Using a variant of triangle width, we prove that a F 2||C max generalization is polynomial. To the best of authors knowledge, this variant have not been studied before.

We consider a generalization of F 2||C max where we allow some overlap between task i on machine 1 and task i on machine 2, denoted by t i . This problem

m2 m1 i j Pi2 Pj1 m i n ( P j 1 , P i 2 ) m2 m1 j i Pj2 Pi1 m i n ( P i 1 , P j 2 ) min(Pj1, Pi2) ≥ min(Pi1, Pj2)
Fig. 10: Exchange argument for Johnson's rule using triangle width visualization can be easily seen using a variation of triangle width. We now consider rectangles with an empty triangle where the size of this triangle is t i . Using this representation, we can use the same argument used to prove Johnson's rule.

Theorem 7 There exists a dominant permutation that schedules tasks i before j if min(P j1 + t i , P i2 + t j ) ≥ min(P i1 + t j , P j2 + t i ).

Proof. First, we prove by contradiction that there exists a dominant permutation schedule, using the same argument for F 2||C max (see [Pin16]). Suppose that no optimal permutation schedule exists. An optimal (non-permutation) schedule has two tasks i, j such that i is scheduled before j on the input machine and j is scheduled before i on the output machine. We can construct another solution by scheduling i just before j on the output machine. The new solution is feasible since every task but i is postponed on the output machine. Also, no task before the end of j on the output machine is postponed, thus, the new solution is also optimal. Hence the contradiction. Now, let us prove that if i is scheduled before j and min(P j1 + t i , P i2 + t j ) > min(P i1 + t j , P j2 + t i ), the schedule is not optimal. As illustrated in Figure 11, permuting i and j strictly increase the objective function. Thus a schedule where i is before j and min(P j1 + t i , P i2 + t j ) > min(P i1 + t j , P j2 + t i ) is not dominant.

Corollary 2. There exists a polynomial time greedy algorithm that solves F 2|t j ∈ [-min(p 1j , p 2j ), 0]|C max .

Finally, we note that [Mit59] proposes a related (but different) generalization of Johnson's argument for F 2||C max . It considers positive time lags and permutation flowshops.

Conclusion

In this paper, we introduced a new problem called triangle width. This problem arises in several real life applications (parallel database optimization, embedded Fig. 11: exchange argument for generalized Johnson's rule using triangle width visualization.

vision system optimization etc.). It is also related to some interesting theoretical questions such as the binary matrix permutation and weak k-visit. We presented it under 3 formulations: a 2 parallel machine scheduling problem which objective is to minimize the makespan, a matrix visualization problem which the objective is to maximize an empty "upper-right triangle" and a vertex ordering problem in a hypergraph where vertices are investments, hyper-edges projects and the objective is to minimize the initial required treasury. The problem turns out to be N P-Hard even if the hypergraph is a graph and vertices cost more than the edges (if the vertices cost less than the edges, the problem is polynomial). If all vertices and edges cost the same, the problem is N P-Hard. Finally, we gave a short proof that the triangular matrix permutation problem is N P-Hard and a visual argument of Johnson's algorithm for F 2||C max . This visual argument also helped to find and prove a new generalization of Johnson's rule for the 2 machine flowshop problem with negative time lags.

Fig. 1 :

 1 Fig. 1: Example of a treasury diagram where we trace the evolution of the treasury upon projects completion

Fig. 2 :

 2 Fig. 2: Another example of a treasury diagram where investments cost money and project produce money

Fig. 3 :

 3 Fig. 3: Vertex ordering solution where the treasury initial capacity b = 5.

-Fig. 4 :

 4 Fig. 4: Example of a feasible schedule

Fig. 5 :

 5 Fig. 5: Example of binary matrix visualization problem. Each row (resp. column) has its own height (resp. width).

Fig. 7 :

 7 Fig. 7: Matrix where columns are duplicated to simulate a duration of 2 for each column

Fig. 8 :

 8 Fig.8: Example of the matrix used to prove that solving the matrix triangular problem also solves triangle width with a = 1

Fig. 9 :

 9 Fig.9: Visual Argument of equivalence between the formalization using triangle width and F 2||C max .

  Triangle Width: between graph theory, scheduling and matrix visualization XVII

	i	ti	j Pj1 j 1 + m i n ( P t i , P i 2 +	Pi2 tj t j )	m2	j	m1 tj m i n ( P i 1 + Pi1 i t j , P j 2 + Pj2 ti t i )
	min(Pj1 + ti, Pi2 + tj)	≥	min(Pi1 + tj, Pj2 + ti)

When a > 1 k-1 , the status of the complexity of the problem is open.

F 2||C max and Johnson's algorithm

We quickly recall F 2||C max . Consider two machines (m 1 , m 2 ), n tasks (T ) with p i1 (resp p i2 ) the duration of task i on m 1 (resp. on m 2 ). Each task needs to be scheduled first on m 1 , then on m 2 . The goal is to find an order σ on the tasks which minimizes the total completion time (makespan or C max ). Johnson's rule (see [Pin16]) consists in sorting tasks with the criterion min(P j1 , P i2 ) ≥ min(P i1 , P j2 ) =⇒ i is scheduled before j. This leads to an optimal greedy algorithm for F 2||C max .

We show that triangle width is a generalization of F 2||C max . We use the matrix representation to illustrate and give a visual proof of Johnson's algorithm. Moreover, using this representation, we are able to generalize Johnson's argument and obtain a new rule for F 2||C max with negative time-lags (i.e. task i on machine 2 can start before the end of task i on machine 1).

F 2||C max We construct the triangle width as follows:

We see the triangle width instance as a series of consecutive black blocks. The length of a block is its computation time on machine 1 (and the height of a block its computation time on machine 2). The diagonal line crossing the origin (start of the first task (a)) indicates times where machines 1 and 2 have the same


Wenjuan Wang

Shuang Chen

Eduardo Guisasola Cal

Marta Martínez Moro

Sergio Moya

Emerson Coy

Changlong Wang

Jean-René Hamon

Didier Astruc
email: didier.astruc@u-bordeaux.fr

ZIF-8-Based vs. ZIF-8-Derived Au and Pd Nanoparticles as Efficient Catalysts for the Ullmann Homocoupling Reaction

Keywords: UV-vis, XPS, 1

The Ullmann coupling reaction of aromatic halides is the most challenging C-C coupling reactions. Both MOF-based and MOF-derived types of catalysts have recently provided useful nanocatalysts for a variety of reactions, but they have rarely been compared. Here Ullmann-type aryl iodides homocoupling is efficiently catalyzed by gold and palladium nanoparticles (NPs) loaded on ZIF-8 before (ZIF-8-based nanocatalyst: M@ZIF-8) and after calcination (ZIF-8derived catalyst: M@CN). The nanocatalysts M@ZIF-8 (M = Pd, Au) are found to be more efficient than the catalysts M@CN. Pd@ZIF-8 shows better performances than those of Au@ZIF-8 for a series of aryl iodides, but in the case of 4-nitro-iodobenzene, deshydroiodination was observed besides the coupling product. Mechanisms are proposed and discussed for both Au(0) and Pd(0) nanocatalysts.

Introduction

The Ullmann reaction involving aryl halide coupling to biaryl has attracted attention for over a century, 1 in particular given the synthetic interest of biaryl compounds, [START_REF] Evano | Copper-mediated coupling reactions and their applications in natural products and designed biomolecules synthesis[END_REF][START_REF] Bringmann | Atroposelective total synthesis of axially chiral biaryl natural products[END_REF][START_REF] Aldemir | The biocatalytic repertoire of natural biaryl formation[END_REF] and the area has been the subject of excellent reviews. [START_REF] Hassan | Aryl-aryl bond formation one century after the discovery of the Ullmann reaction[END_REF][START_REF] Beletskaya | Copper in crosscoupling reactions: the post-Ullmann chemistry[END_REF][START_REF] Corbet | Selected patented crosscoupling reaction technologies[END_REF][START_REF] Alberico | Aryl-aryl bond formation by transition-metal-catalyzed direct arylation[END_REF][START_REF] Sperotto | The mechanism of the modified Ullmann reaction[END_REF][START_REF] Sambiagio | Copper catalysed Ullmann type chemistry: from mechanistic aspects to modern development[END_REF][START_REF] Fan | Surface-catalyzed C-C covalent coupling strategies toward the synthesis of lowdimensional carbon-based nanostructures[END_REF][START_REF]Recent advancement of Ullmann-type coupling reactions in the formation of C-C bond[END_REF][START_REF] Zhou | A Critical review on carbon-carbon coupling over ultra-small gold nanoclusters[END_REF] This reaction was well-known to be catalyzed by large amounts of copper catalyst, to require temperature higher than 200°C and to undergo extensive hydrodehalogenation as a side reaction.

During the last decade, however, efforts have been devoted to circumvent direct aryl halide coupling and to use sophisticated Pd-based or Au-based catalysts. [START_REF] Hassan | Aryl-aryl bond formation one century after the discovery of the Ullmann reaction[END_REF][START_REF] Beletskaya | Copper in crosscoupling reactions: the post-Ullmann chemistry[END_REF][START_REF] Corbet | Selected patented crosscoupling reaction technologies[END_REF][START_REF] Alberico | Aryl-aryl bond formation by transition-metal-catalyzed direct arylation[END_REF][START_REF] Sperotto | The mechanism of the modified Ullmann reaction[END_REF][START_REF] Sambiagio | Copper catalysed Ullmann type chemistry: from mechanistic aspects to modern development[END_REF][START_REF] Fan | Surface-catalyzed C-C covalent coupling strategies toward the synthesis of lowdimensional carbon-based nanostructures[END_REF][START_REF]Recent advancement of Ullmann-type coupling reactions in the formation of C-C bond[END_REF][START_REF] Zhou | A Critical review on carbon-carbon coupling over ultra-small gold nanoclusters[END_REF] Au nanoparticles (NP) 14-18 in particular were shown to be tentative catalysts. Jin's group has shown in several publications that small precisely molecularly defined Au nanoclusters covered with thiolate ligands were excellent catalysts of Ullmann coupling.

15-18

Rodionov's group demonstrated that a combination of thiolate groups and linear semi-fluorinated chains effectively stabilized the NPs against aggregation, while preserving the catalytic activity of AuNPs. [START_REF] Chen | Thiols make for better catalysts: Au nanoparticles supported on functional SBA-15 for catalysis of Ullmann-type homocouplings[END_REF] Various other reports using AuNP catalysts 20-24 have been recently and comprehensively reviewed by Ding's group, [START_REF] Jiang | Aryl-aryl bond formation by Ullmann reaction: from mechanistic aspects to catalyst[END_REF] and particular attention to carboncarbon bond formation catalysts has been drawn by Garcia's group to the use of MOF-based catalysts. 26,[START_REF] Wang | State of the art and prospects in metal-organic framework (MOF)-based and MOF-derived nanocatalysis[END_REF] NP catalysts are indeed particularly efficient for a large variety of reactions and withstand homogeneous as well as heterogeneous reaction conditions. They present the great advantages of simple preparation by reduction of a metal salt, and do not require costly, sophisticated, and toxic ligands. 28-37 MOF supports, particularly of ZIF-8 type have recently been particularly successful in the field of hydrogen generation and a number of other organic reactions. 27,38,39 29 MOFs are used in catalysis as templates that are all the more efficient as they act in synergy with NP catalysts (MOF-based catalysts). They also serve to form porous, very active N-doped conducting carbon supports ("CN") upon pyrolysis at high temperature such as 900°C, in which case they are classified as MOF-derived heterogeneous catalysts. Given the recent interest in both MOF-based and MOF-derived catalysts, [START_REF] Zhao | Highly efficient heterogeneous catalytic materials derived from metal-organic framework supports/precursors[END_REF][START_REF] Shen | Development of MOF-derived carbon-based nanomaterials for efficient catalysis[END_REF] here the efficiency and recyclability of ZIF-8-based and ZIF-8-derived catalysts in synergy with Au and Pd NPs for Ullmann homocoupling are compared. In this study ZIF-8-supported AuNPs and PdNPs are also compared, and optimization of the reaction conditions was conducted for the coupling of substituted aryl iodides.

Results

Fabrication and characterization of the support and catalysts

First, ZIF-8 [START_REF] Park | Exceptional chemical and thermal stability of zeolitic imidazolate frameworks[END_REF] was fabricated in methanol by an established method [START_REF] Cravillon | Controlling zeolitic imidazolate framework nano-and microcrystal formation: insight into crystal growth by time-resolved in situ static light scattering[END_REF] (Supporting Information). According to the TEM of the as-prepared Au@ZIF-8, the AuNPs are homogeneously loaded on hexagonal ZIF-8 (Fig. 2a) with a mean size of 3.4 nm (Fig. 2b insert). In the TEM of Pd@ZIF-8 (Fig. 2c), it is not easy to observe the PdNPs on the ZIF-8 support. Therefore, a common method, digestion of the nanocatalyst with EDTA to release nanoparticles that are further stabilized by PVP, was used to obtain the average size of Pd@ZIF-8: 2.31 nm as shown in Fig. 2d insert, which is smaller than Au@ZIF-8.

Compared with ZIF-8, no peak of either Pd NP or Au NP species was observed in the X-ray powder diffraction (PXRD) patterns after reduction (Fig. S5), which implies that both Pd@ZIF-8 and Au@ZIF-8 have a too low Au loading or an ultra-small size.

44,45

X-ray photoelectron spectroscopy (XPS) was employed to check the metal oxidation state and composition. XPS results revealed the presence of Zn, Pd, O, C and N in the catalyst Pd@ZIF-8 (Fig. S6a). As shown in Fig. S6b, the well-defined peaks at 335.2 and 340.7 eV corresponding to Pd (0) 3d 5/2 and Pd (0) 3d 3/2 , and two peaks at 338.1 and 343.7 eV are also observed for Pd(II) 2p 5/2 and Pd(II) 2p 3/2 respectively. For Au@ZIF-8, similar elements, Zn, O, C and N are observed from Fig. S6c. The peaks at 83.6 and 87.3 eV belong to Au (0) 4f 7/2 and Au (0) 4f 5/2 , and two peaks at 88.7 and 90.8 eV are also observed for Zn (II) 2p 3/2 and Zn (II) 2p 1/2 respectively (Fig. S6d).

Fig. 2 Nitrogen adsorption-desorption isotherms of ZIF-8, Au@ZIF-8 and Pd@ZIF-8. , respectively (Fig. 2 and Table S1). This appreciable decrease means that the pores of ZIF-8 are embedded with MNPs or/and covered by MNPs loading on the surface. In order to optimize the reaction conditions, iodobenzene was first chosen as the model substrate for the classical Ullmann C-C homocoupling reaction, Au@ZIF-8 (with various Au loadings) as catalyst, K 2 CO 3 as a base and dimethyl formamide (DMF) as solvent at 130 o C under N 2 atmosphere for 2 days.

Catalytic activity

According to the 1 H NMR results, the conversion of iodobenzene increased slightly from 76% to 83% with the amount of Au changing from 6 mmol% to 12 mmol% (Table 1, entries 1-2). Under the same conditions, Pd@ZIF-8 even with 6 mmol% of Pd exhibits a behavior analogous to Au@ZIF-8 with twice more metal loading (Table 1, entries 3). In addition, the nanocatalyst Pd@ZIF-8 with 1.35 and 5.4 wt% of Pd loading (Table 1, entries 4,5) was used to optimize the metal loading rate. The 1 H NMR results indicate that 2.7 wt% of Pd is good enough to get an excellent conversion to iodobenzene. Then different catalysts were applied in the above model reaction, and the MOF-based catalysts Au@ZIF-8 and Pd@ZIF-8 with the same metal loading showed an excellent catalytic performance under the same conditions. Interestingly, the catalytic activity of MOF-derived catalysts with larger sizes considerably decreased (Table 1, entries 7,8) after calcination of M@ZIF-8 at 900 o C under N 2 , which may be due to the aggregation of MNPs. In control experiments, no reaction occurred using the support ZIF-8 or CN as the only catalyst (Table 1, entries 6,9). In light of the above results, Au@ZIF-8 and Pd@ZIF-8 were chosen as catalysts to further investigate and optimize catalytic performances and screen out the reaction conditions. With Au@ZIF-8 the investigation of the optimal reaction temperature in this Ullmann homocoupling reaction included conducting the model reaction at 110 o C and 140 o C (Table S2, entry 2-3), and it was found that Au@ZIF-8 worked best at 140 o C. Two other solvents with high boiling point (xylene and PEG-400) were probed for the reaction (Table S2, entries 4-5), but they were not as satisfactory as DMF (Table S2, entry 3). In particular, the reactions using toluene produced poor yields. Indeed, the reaction stoichiometry required the consumption of two electrons, and DMF and alcohols are good electron donors at such high temperature, whereas toluene is not. Thus, DMF that contributes to the stabilization of the NPs also acts as a reductant. Among the different bases that were probed in this system including K 2 CO 3 and K 3 PO 4 (Table S2, entries 3, 6), the catalyst Au@ZIF-8 showed the best conversion efficiency (83%) with K 3 PO 4 . Analogous studies were also conducted with Finally, the scope of the substrates was extended under these optimized reaction conditions. As shown in table 3, 100% of 4iodo-toluene, 100% of 4-iodo-anisole and 67% of 4-chloroiodobenzene are consumed to form the final product 4,4'dimethoxy-1,1'-biphenyl, 4,4'-dimethyl-1,1'-biphenyl and 4,4'dichloro-1,1'-biphenyl (Table 3). With Au@ZIF-8 as the catalyst, however, in comparison with the conversions above, a lower yield for each electron-rich substrate than with Pd@ZIF-8 was obtained (Table 3), which further demonstrated that Pd@ZIF-8 was the best catalyst. For the electron-deficient substrates, however, Au@ZIF-8 and Pd@ZIF-8 show a similar performance. The case of 1-iodo-4-nitrobenzene was found to be special. The substrate was totally consumed at 140°C, but the yield of coupled product was only 50% with 50% of the side product Table 3. Homocoupling of aryl iodides by Pd@ZIF-8 (Au@ZIF-8). nitrobenzene resulting from dehydrohalogenation that was not found with the other p-substituted iodoarenes examined. This result is similar to the case of Au@ZIF-8.

Recyclability of Au@ZIF-8 and Pd@ZIF-8

The conversion of iodobenzene decreased from 100% to 75% after the recycling of Pd@ZIF-8 for the model reaction, which can probably be ascribed to the loss of some Pd species (Fig. S7a) It was found by TEM, however, that after the reaction PdNPs became larger (Table 4 and Fig. S4). For Au@ZIF-8, the conversion decreased a lot from 83% to be 43% after the 1st cycle, which is due to the size of AuNPs with a remarkable increase and serious aggregation (Table 4 and Fig. S5). Besides, the signal of Au(0) of Au@ZIF-8 decreased in the XPS spectrum (Fig. S7b). Moreover, both Au@ ZIF-8 and Pd@ZIF-8 suffer from leaching as observed by the yellow color of the solution after the reaction. For the ZIF-8 derived nanocatalyst, the recycling yield is very low, 20% for Au@CN and 9% for Pd@CN (Table 4).

Discussion

Mechanistic discussions on Ullmann coupling catalyzed by inorganic complexes have been reviewed by de Vries and van Koten. [START_REF] Sperotto | The mechanism of the modified Ullmann reaction[END_REF] Here the specificity of the metal (0) NP catalysts is discussed. The rather high temperature needed for the Ullmann reaction results from the absence of transmetalation step [START_REF] Yurderi | Ruthenium(0) nanoparticles stabilized by metal-organic framework (ZIF-8): Highly efficient catalyst for the dehydrogenation of dimethylamine-borane and transfer hydrogenation of unsaturated hydrocarbons using dimethylamine-borane as hydrogen source[END_REF] that renders C-C coupling facile in other cross coupling reaction of aryl halides with organoboron and other organometallic reagents. The difficulty in Ullmann coupling is the double oxidative addition of the aryl halide that requires the intermediacy of high oxidation states with monometallic catalysts. [START_REF] Kochi | Organometallic Mechanisms and Catalysis[END_REF] Another crucial problem is that this oxidative addition requires the presence of classic reductant of the metal intermediate species to the starting zero oxidation state. [START_REF] Astruc | Electron Transfer and Radical Processes in Transition Metal Chemistry[END_REF] With PdNPs, it is well known that the leaching mechanism observed here is most often encountered in carbon-carbon coupling reaction, even when they are much more facile. [START_REF] Reetz | Ligand-free Heck reactions using low Pd-loading[END_REF] Here the high temperature needed for the reaction renders the integrity of the NP doubtful, and the considerable structural change of the NP sizes along the reaction as well as the observed leaching of the PdNPs show that atoms and small clusters of atoms are formed along the reaction pathways.

Thus, it is difficult to claim the actual NP or cluster size during the catalytic events. Under the reaction conditions, the surface Au and Pd atoms are shown by XPS to be in the zero-oxidation state, which is expected given the full reduction of the cationic precursors and the L (2-electron)-ligand nature of the DMF ligands. It is well known that oxidative addition of aryl iodides is easy on Pd(0) to start the catalytic cycles, and that the Pd oxidation states involved are 0 and II, i.e. that inner-sphere two-electron transfers are involved in the catalytic steps. Such is not the case for the starting Au(0) that can only undergo single-electron transfer to Au(I), eventually before further oxidative addition to Au(III). Thus, we suggest that the AuNP first acts as reductant of Ar-X in the initial step. Such a step is endergonic, but it becomes possible at high temperature, singleelectron transfers being favored at high temperature, especially given the irreversibility of the follow-up step. The redox step generates X -, Ar . and [Au n ] + , and it is followed by cage coupling between the above radical cage followed by hydrogen atom abstraction from the solvent. Indeed the life time of the nitrophenyl radical is considerably prolonged compared to the phenyl radical and other aryl radicals due to the pelectronic delocalization provided by the nitro group. This observation of the dehydrohalogenation in this particular case somewhat confirms the proposal of aryl iodide reduction producing the radical cage in this first step. The overall stoichiometry of the Ullmann coupling requires two electrons (equation 1), which means that the only possible stoichiometric electron donor is the solvent (DMF and alcohols).

2 ArI + 2e - Ar-Ar + 2 I - ( equation 1)
The solvents DMF (that is oxidized in situ to Me 2 NH and CO 2 ) 49 and PEG are known to be good electron donors, and they are indeed presently suitable and favorable contrary to toluene. Note that DMF plays multiple roles as solvent, stabilizing 2electron L ligand and reducing agent. DMF has even been used to serve as reducing agent of transition metal cations for the formation of NPs, in particular Ag + to Ag 0 , [START_REF] Pastoriza-Santos | N-Dimethylformamide as a reaction medium for metal nanoparticle synthesis[END_REF] which shows its ability to serve in single-electron transfer steps.

We suggest that with PdNPs this reducing function is used in the last step of the catalytic cycle (most probably decomposed in two successive single-electron transfer steps) and in the steps involving reduction of cationic AuNP to neutral species in the cycle with AuNP. These endergonic redox steps of the cycles are most probably the rate-limiting steps of the overall reactions and responsible for the high temperatures required for these Ullmann coupling with both the AuNP and PdNP catalysts. It is interesting that dehydroiodination of 4-nitroiodobenzene also intervenes in the PdNP-catalyzed reaction, as in the case of AuNP, although to a lower extent. This indicates that reduction of this easily reducible substrate (because of the strongly electron withdrawing nitro group) occurs in competition with oxidative addition onto Pd(0) at this high reaction temperature. The optimization of the base used in the reactions ended up in the finding that K 3 PO 4 was the best base in terms of performance. In fact, the so-called "base" does not function as a base but as a salt in which the electrostatic bonding between the anion and the cation plays the key role in the iodide removal from the metal creating new ion pairs as shown in scheme 2. Thus, it is the relative ion pairing strengths among the distinct ion pairs involved in the catalytic cycle that play the decisive role in the rate of the reaction.

50,51

The comparison between ZIF-8-based catalysts and ZIF-8derived that had to our knowledge not been recorded earlier provides, under the same conditions, yields that are almost quantitative with ZIF-8 based catalysts and significantly or sharply lower with ZIF-8-derived catalysts. It is possible that the confinement in ZIF-8-based catalysts provides a better stability and efficiency of the NPs than the ZIF-8 derived catalyst for the Ullmann reaction that requires harsh conditions. Therefore, the ZIF-8-based and ZIF-8-derived nanocatalysts have been examined for both Au and Pd.

In comparison with Pd@CN, Pd@ZIF-8 shows a much better performance in the same conditions, but with Pd@ZIF-8 leaching prevents efficient recycling. However, both Au@ZIF-8 and Au@CN display a similar conversion.

Experimental General data

Preparation of ZIF-8. spectroscopy (ICP-AES). The ICP result showed that there was 4.5 wt % Au in Au@ZIF-8 and 2.3 wt% Pd in Pd@ZIF-8.

Preparation of Au@CN and Pd@CN.

The powder of Au@ZIF-8 (or Pd@ZIF-8) sample was placed in a tube furnace, then heated to 900 o C for 2 h with a heating rate of 5 o C min -1 under a flow of N 2 before cooling to rt providing Au@CN (or Pd@CN).

Application in catalysis

A 10-mL Schlenk tube was charged with a magnetic bar, 50 mg M@ZIF-8 or 20 mg M@CN, 0.6 mmol K 3 PO 4 , 0.2 mmol aryl iodides and 1mL DMF and purged with N 2 for 10 minutes. Then the mixture was heated at 140°C for 48 h, and after cooling down to rt, the reaction mixture was filtered. The liquid was extracted several times with dichloromethane and water in order to remove DMF. The organic phase was dried over Na 2 SO 4 , then CH 2 Cl 2 was removed under reduced pressure at the rotary evaporator providing the crude product. Finally, the result of the homocoupling Ullmann reaction was monitored via 1 H NMR (300 MHz, CDCl 3 ).

Conclusion

The carbon-carbon homocoupling of various aryl iodides is efficiently catalyzed by MOF-based metal NPs and MOFderived metal NPs, but the MOF-based nanocatalysts perform better than the related MOF-derived catalysts (MOF = ZIF-8).

Both PdNPs and AuNPs are efficient, although the ZIF-8-based PdNPs are slightly better than their nanogold analogues. With these results in hand, mechanisms are proposed for both the Pd(0) and Au(0) nanocatalysts. Since the stoichiometry of the Ullmann reaction requires two electrons, these electrons are provided by the DMF and PEG-400 that are good reductants, whereas poor reductants such as toluene give bad coupling yields. The difference between the catalytic cycles of the Pd(0)-catalyzed and Au(0)-catalyzed reactions must take into account the fact that Pd(0) readily give rise to oxidative addition with increase of two units of the metal oxidation state, whereas Au(0) does not. Thus, double oxidative addition occurs at the beginning of the cycle with Pd(0), whereas the Au(0) cycle must start by reduction of the aryl iodide providing an Au(I)-aryl bond. The double oxidative addition on Pd(0) probably does not reach Pd(IV), but may more easily and successively occur on two distinct Pd(0) atoms of the PdNP surface to give rise to two Pd(II)-aryl species from which arylaryl reductive elimination occurs (eventually following some "walk" of the aryl ligands on the Pd surface until reaching each other to reductively eliminate). In both the Pd and Au catalytic cycles, the two electrons are transferred stepwise (see Scheme 2). Finally, these results with NPs may be compared with the remarkable results obtained by Jin's group with Au 25 nanoclusters that were obtained under slightly milder conditions. One major difference is that with the Au 25 nanoclusters, the sulfide-bonded Au atoms are in the oxidation state Au(I), thus in principle the difficult Au(0)  (Au(I) step of Scheme 2 is not required in the case of the nanocluster catalysts. This may represent one of the significant advantages of the use of the Au 25 nanoclusters. Note that a similar situation was reached by Rodionov et al in their use of thiolate-stabilized AuNPs. In conclusion the excellent coupling results and comparison between ZIF-8 based and ZIF-8 derived templates of AuNPs and PdNPs and the comparison between the AuNP and PdNP catalysts together with the scrutiny of the optimized temperature, base and solvent allow a better understanding of the optimization and mechanisms of the Ullmann coupling reactions and their potential applications.

A c c e p t e d M a n u s c r i p t under N 2 Scheme 1 .

 21 Scheme 1. Synthesis of the M@ZIF-8 and M@CN (M= Au, Pd).

Fig. 2

 2 Fig. 2 TEM images of Au@ZIF-8; a and b (the insert is the size distribution histogram of Au@ZIF-8) and Pd@ZIF-8 (c). d) TEM image and size distribution of Pd@ZIF-8 after digestion of the nanocatalyst with ethylenediamine tetracetic acid (EDTA) to release nanoparticles, and nanoparticles stabilized by PVP.

A c c e p t e d M a n u s c r i p t Scheme 2 .

 2 Scheme 2. Proposed catalytic cycles for the Ullmann homocoupling reaction catalyzed by Au@ZIF-8(a) and Pd@ZIF-8(b). The small colored spheres represent a NP, not a single atom (except if single leached atoms are involved). Coordination of ligands in the catalytic cycle may involve several surface atoms of the NP or cluster, and the aryl ligands may "walk" on the surfaces towards gathering for reductive elimination.

42 2 -

 2 Methylimidazole (75 mmol, 6.16 g) was dissolved in 150 mL methanol at room temperature (R.T.) forming a clear solution in flask A. Zn(NO 3 ) 2 •6H 2 O (20 mmol, 6.02 g) was dissolved in 150 mL methanol in the flask B. Then the solution in the flask B was added into flask A. After 1 day, the white suspension was collected by centrifugation and washed by methanol three times. ZIF-ZIF-8 was dispersed in 5 mL methanol under ultrasound for 5 min, then 1 mL aqueous solution with 5 mg metal (HAuCl 4 •3H 2 O or Na 2 PdCl 4 ) and 4 mL deionized water were added respectively, and the mixture was submitted to ultrasound for another 5 min. Then stirring was continued for 30 min at room temperature (rt). Then, 1 mL aqueous solution of fresh NaBH 4 (10 equiv. per metal) was rapidly injected under vigorous stirring. After 30 min, the final product was collected by centrifugation at 10000 r.p.m. for 10 min. and washed three times with deionized water, then dried at 60 o C in vacuo overnight. The metal content was quantified by inductively coupled plasma atomic emission

  A c c e p t e d M a n u s c r i p t

Table 1 .

 1 Iodobenzene coupling catalyzed by various catalysts.

Catalyst, K 2 CO 3 DMF, 130 o C, Time I 2

	Reaction conditions: 0.2 mmol iodobenzene, 0.6 mmol K2CO3, 1 mL DMF, 50 mg
	M@ZIF-8, 130 o C, N2.	a M@ZIF-8 pyrolyzed at 900	o C for 2 h under N2, 20 mg M@CN.	b
	1 H NMR conversion.
	N 2 physisorption measurements of Brunauer-Emmett-Teller
	(BET) surface areas for ZIF-8, Pd@ZIF-8 and Au@ZIF-8 were
	determined to be 1365.1, 1247.7 and 1283.1 m 2 g -1

Table 2 .

 2 Effects of base and temperature on the homocoupling of iodobenzene catalyzed by Pd@ZIF-8.

	2	I	Pd@ZIF-8, base DMF, Temp. o C, Time
	Entry	Base	Time (h)	Temp. ( o C)	Conversion (%) a
	1	K2CO3	24	130	33
	2	K2CO3	48	130	86
	3	K3PO4	48	130	92
	4	K3PO4	48	140	100
	Reaction conditions: 0.2 mmol iodobenzene, 0.6 mmol base, 1 mL solvent, 50 mg
	Pd@ZIF-8 (6 mmol% Pd), N2. a 1 H NMR conversion.
	Pd@ZIF-8. It was shown that Pd@ZIF-8 best cooperated with
	K 3 PO 4 to catalyze the model reaction at 140	o C for 2 days (Table
	2, entries 1-4).

M@ZIF-8, K 3 PO 4 DMF, 140 o C, 48 h

	Cl	I	Cl	Cl		62	67
	O 2 N	I	O 2 N	NO 2	100 (47 b + 53 c )	100 (50 b + 50 c )
	Reaction conditions: 0.2 mmol substrate, 0.6 mmol K3PO4, 1 mL DMF, 50 mg M@ZIF-8 (6 mmol% metal), 140	o C, N2, 48 h.	a 1 H NMR conversion.
			M a n u s c r i p t
	I A c c e p t e d 2 R Substrate Product I		R	R Conversion (%) a Au@ZIF-8 Pd@ZIF-8 83 100
	H 3 C	I	H 3 C	CH 3		70	100
	H 3 CO	I	H 3 CO	OCH 3		68	100

b Yield of C-C homocoupling. c Yield of dehydrohalogenation.

Table 4 .

 4 Sizes and catalytic efficiencies of the nanocatalysts

						a
			Catalyst, K 3 PO 4
	2	I	DMF, 140 o C, 48 h
	Catalyst	Size b (nm)	Size c (nm)	Conversion (%) d	Conversion-1 st Cycle (%) e
	Au@ZIF-8	3.20	23.14	83	54
	Au@CN f	4.39	/	40	20
	Pd@ZIF-8	2.31	3.16	100	75
	Pd@CN f	5.64	/	13	9
	a Reaction conditions: 0.2 mmol iodobenzene, 0.6 mmol K3PO4, 1 mL DMF, 50 mg
	M@ZIF-8 (6 mmol% metal), 140 o C, N2, 48 h. TEM size before reaction (size	b ) and after
	reaction (size c ).	d 1 H NMR conversion.

e Conversion after the 1rst cycle. f 20 mg M@CN (6.5 mmol% metal).

Acknowledgements

Financial support from the China Scholarship Council of the People's Republic of China (PhD grant to W. W.), the University of Bordeaux, the Centre National de la Recherche Scientifique (CNRS) and CIC biomaGUNE is gratefully acknowledged.

Conflicts of interest

The authors declare no competing financial interest.

Table of content