Emma Effa

Laurent Wouters
email: lwouters@cenotelie.fr

Marie-Pierre Gervais
email: marie-pierre.gervais@lip6.fr

Ali Koudri
email: ali.koudri@irt-systemx.fr

Reda Bendraou
email: reda.bendraou@lip6.fr

Semi-supervised Approach for Recovering Traceability Links in Complex Systems

Keywords: traceability, information retrieval, requirements, models, complex systems I

Building a complex system requires the collaboration of different stakeholders. They work together to model the system keeping in mind the requirements described in specification documents. This complexity induces a large volume of requirements and models, i.e., artefacts that will be subject to frequent changes during the project lifetime. Since the artefacts are correlated with each other's, each change has to be rigorously propagated. Identifying traceability links between system's artefacts is then a critical step to reach this goal. In Information Retrieval domain, many approaches have been already proposed to cope with traceability issues. Their main drawback is they introduce an important amount of false positive links making the traceability links validation phase time consuming and error-prone. In this paper, we propose an approach that identifies traceability links with a reduced amount of false positive links ranging from 20% to 30% while raising the amount of true links identified up to 70%. The approach consists of three main steps: 1) we measure syntactical and semantic similarities between pairs of artefacts by combining the use of four major Information Retrieval techniques; 2) using these similarity measures, we identify the most likely true and false links and we build the so called training data set; 3) this training data set and the four IR techniques are used as input of a predictive model in order to classify between true and false links leading ultimately to a reduced amount of false positives. The output is given in the form of a confidence measure that will help the modeller validating the traceability links. We evaluated our approach using four well-known public case studies. Each one comes with a clear identification of true traceability links which allowed us to compare with the outcome of our approach and validate its effectiveness.

INTRODUCTION

The development of complex systems involves the collaboration of many stakeholders. In order to design the system, they produce many artefacts i.e., requirements and models that are correlated with each other's and which evolve constantly. In such a volatile environment, there is a critical need to manage the impact of the different changes occurring during the project lifetime. Traceability, as defined by Edwards and Howell [START_REF] Edwards | A methodology for systems requirements specification and traceability for large real time complex systems[END_REF], is "A technique used to provide a relationship between the requirements, the design and the final implementation of the system." In complex systems engineering, establishing such traceability involves dealing with a large volume of requirements and models [START_REF] Gotel | The grand challenge of traceability (v1. 0)[END_REF]. For example, the full specification of an aircraft includes about 10,000 requirements and a subway line of about 6,000. And modelling an aircraft can lead to hundreds of thousands of elements in hundreds of different models. Dealing manually with traceability issues in such a context is obviously unbearable.

In the literature, many works propose to automate the identification of traceability links. In the Information Retrieval (IR) community, approaches such as Vector Space Model (VSM), Latent Semantic Indexing (LSI), and Latent Dirichlet Allocation (LDA) have been used to recover traceability links between artefacts. However, traceability identification in these approaches is still complex and error prone [START_REF] Heindl | A case study on value-based requirements tracing[END_REF]. Due to that limited accuracy, candidate links are systematically checked by an analyst which manually classifies them into two groups: the approved links called true links and the rejected ones called false links. Thereby, the candidate links evaluation is itself labour intensive and time-consuming [START_REF] Cuddeback | Towards overcoming human analyst fallibility in the requirements tracing process (NIER Track)[END_REF] due to the significant number of false links that represent 90% of the candidate links at a low threshold.

Our approach aims at improving the evaluation of candidate links process by reducing the number of false links retrieved by IR techniques while maintaining a significant number of true links. It belongs to the semi-supervised approaches category as it makes use of links that are not yet validated in conjunction with a small training set. However, in our industrial context, when we start a development project of a complex system, such a training set does not exist. Therefore, our proposal includes the definition of a strategy to build a small training data set.

The approach consists of 3 phases. First, we combine syntactical and semantics similarities measures of four IR techniques, i.e. LSI [START_REF] Wang | Recovering relationships between documentation and source code based on the characteristics of software engineering[END_REF], VSM [START_REF] Chen | A combination approach for enhancing automated traceability:(NIER track)[END_REF][START_REF] Niu | Enhancing candidate link generation for requirements tracing: the cluster hypothesis revisited[END_REF], LDA [START_REF] Panichella | How to effectively use topic models for software engineering tasks? an approach based on genetic algorithms[END_REF] and word embedding [START_REF] Guo | Semantically enhanced software traceability using deep learning techniques[END_REF]. Second, we use these similarities measures to build a small training data set. Finally, this training data set and the four IR techniques are used as input of a predictive model [START_REF] Delalleau | Efficient Non-Parametric Function Induction in Semi-Supervised Learning[END_REF] in order to classify true and false links.

We evaluate our approach by investigating four opensource datasets. The results are very promising and show a reduced amount of false positive links ranging from 20% to 30% while maintaining the amount of true links up to 70%.

The remainder of this paper is organized as follows. Section II describes the overview of the approach. Section III presents the results of a preliminary evaluation of the approach on four public case studies. Section IV discusses related works. Finally, Section V concludes the paper and describes directions for future work.

II. OVERVIEW OF THE APPROACH

Fig. 1 presents an overview of our approach for identifying traceability links between artefacts, namely requirements and models. This is based on the combined use of four well-known IR techniques, LSI, LDA, VSM and Word embedding. IR techniques are used to provide similarity measures between pairs of textual software engineering artefacts. Similarity measures are essential to solve pattern classification problems. LSI, LDA and VSM have been intensively used to provide support for several software engineering tasks, and more recently, word embedding has been successfully employed in various natural language processing tasks [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF][START_REF] Kusner | From word embeddings to document distances[END_REF]. Word embedding represents words as vectors of real numbers that capture their contextual semantic meanings.

We illustrate our approach with an example from the Icebreaker dataset, which is one of the dataset used in the Evaluation Section. In this excerpt, there are one requirement R1 "Historical forecast data shall be retrieved as needed" and one class "Weather Forecast GUI" whose attribute is date and operations are set Date(), get Date(), get Forecast-History(), handle-Critical-Forecast() and, get Forecast-Input().

Our approach takes as input requirements document described in natural language and models in XML Metadata Interchange (XMI) format. In Step 1 "Compute similarities", we perform pre-processing of the input data which consists of the tokenization and Stopwords removal. Stopwords [START_REF] Manning | Introduction to information retrieval[END_REF] are tokens that appear so frequently in the artefacts that they become irrelevant for link recovery. This pre-processing is achieved by means of Natural Processing Language functionalities embedded into the IR techniques we use for quantifying similarities between each pair of artefacts. These measurements are based on morphological similarities between terms contained in the artefacts (LSI, VSM), topics proximity of artefacts (LDA) or semantic proximity of terms (word embedding [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF][START_REF] Kusner | From word embeddings to document distances[END_REF]). We then use Word Mover's Distance (WMD) [START_REF] Kusner | From word embeddings to document distances[END_REF] which assesses the distance between a pair of artefacts using word embedding [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. Thus, each similarity measure provides a description of each pair of artefacts according to a given criterion. A vector containing similarity scores is constructed for each pair of potentially related artefacts. As a result, the more the similarity measures are diverse and complementary, the more this vector will contain enough information to decide whether a link exists or not between two given artefacts. Thus, for a pair of artefacts (x, y) with (m1, m2 ..., mp) the similarity measures assigned by the p IR techniques, the associated descriptor vector would be equal to (m1(x, y), m2(x, y)..., mp(x, y)). Each descriptor vector constitutes a row of the descriptor matrix, which is the output of step 1.

In our example, the descriptor vector of the pair of artefacts R1 and the Weather Forecast GUI class with LSI, VSM, LDA and WMD measures is ((0.94)LSI, (0.44)VSM, (0.71)LDA, (1.03)WMD). If a set of validated links would be available, one could use a supervised classification method [START_REF] Mitchell | Machine learning and data mining[END_REF] to derive a statistical model that estimates the probability for two artefacts to be linked, based on their descriptor vector. This probability could constitute a measure of confidence on the traceability link between two artefacts. Indeed, deep learning approaches have recently achieved outstanding performance in the traceability community [START_REF] Guo | Semantically enhanced software traceability using deep learning techniques[END_REF]. However as mentioned earlier, in our industrial context, a training dataset, i.e. a set of artefacts with validated links, is generally not available. In step 2 "Build training set", we propose a heuristic to label some pairs of artefacts as related or non-related. This heuristic is motivated by the statistical ranking of IR techniques [START_REF]Information retrieval: Data structures & algorithms[END_REF], which puts the most likely links on the top and the bad links (false links) to the bottom. Thus, for each similarity measure, we take the pairs of artefacts with a small percentage of the highest and the lowest similarity scores. In the Evaluation Section, we use empirically the 10% highest and the 10% lowest similarity scores respectively. The list of links labelled as true is obtained as the intersection of the set of links having the highest scores and the list of links labelled as false is obtained by the union of the set of links with the lowest scores. At the end of this step, the labels vector is built. Potential true links are represented with the value "1", the false links are represented with the value "0" and the remaining links, called unlabelled links, are represented with the value "-1". In our example, the labels vector belongs to the unlabelled links because of the disparities of the similarity measures therefore it has the value -1.

In step 3 "Classify Links", we use the descriptor matrix and the labels vector as inputs. Based on these inputs, a predictive model finds the community structures in order to group them in true and false links. Given the important amount of unlabelled data, in order to build our predictive model, we use the label spreading method, which is a semisupervised machine learning technique. We use label spreading [START_REF] Delalleau | Efficient Non-Parametric Function Induction in Semi-Supervised Learning[END_REF] among other semi-supervised learning methods because of its ability to modify initially provided labels and therefore, its potential robustness to labelling errors. The label propagation algorithm and its variant the label spreading are used for community detection in large complex networks. Therefore, label spreading efficiency for our problem relies on the clustering hypothesis, which is the assumption that true links tend to gather in the descriptors space [START_REF] Niu | Enhancing candidate link generation for requirements tracing: the cluster hypothesis revisited[END_REF]. As output, the predictive model provides a probability which describes how much a link belongs to the class of true links. As previously stated, we will refer to this probability as a confidence measure. From a practical point of view, it provides a prioritization criterion to the analyst during the links verification phase. In our example, the confidence measure of the requirement R1 and the Weather Forecast GUI class is 0.19.

III. EVALUATION

The experiments for the validation of our approach have been conducted over four datasets available on the COEST1 website: Icebreaker, HIPAA (Healthcare Insurance Portability and Accountability Act), EasyClinic, and CM1-NASA (NASA spacecraft instrument). The Icebreaker dataset was built by students. It provides traceability links between High-level requirements and UML Classes. The HIPAA provides traceability links between 10 HIPAA Technical safeguards and requirements in 10 different requirements specifications. The CM1-NASA is a dataset which provides high-level requirements and low-level requirements documents. The EasyClinic dataset was also built by a small group of students. It contains several artefacts including use cases, interaction diagrams, test cases and classes description.

VSM has been implemented via the Tracelab tool [START_REF] Cleland-Huang | Grand challenges, benchmarks, and TraceLab: developing infrastructure for the software traceability research community[END_REF]. LSI, LDA and WMD have been implemented with Gensim2 . We experimented all the possible combinations of the four IR techniques and the best one in the classification problem was: VSM-LSI-LDA. We compare the performance of this combination against the performance of each individual IR technique. The most used metrics for evaluating any IR techniques are recall, precision and F-measure. F-measure is the harmonic average of the recall and the precision. It shows trade-offs between precision and recall. It can then be used to provide insights about the performance of a method. A pair of artifacts is considered related when the similarity measure is greater or equal to a given threshold. The accuracy rate of IR technique strongly relies on this threshold. Thus, we evaluated the results by plotting Fmeasure at different thresholds for each method on the four datasets. The F-measure results of all methods in Fig. 2, Fig. 3, Fig. 4, and Fig. 5, show that our approach is more effective than VSM, LSI, and LDA at low threshold from 0 to 0.3. Precisions at low thresholds are significantly improved by our approach; especially at low threshold from 0 to 0.3. Our precision is much higher than LSI, VSM and WMD. Concerning to LDA, it depends on the chosen threshold. The higher the threshold, the better LDA is compared to our approach. Concerning the recall, our approach is lower at high thresholds from 0.3 to 0.9. Nevertheless, our approach achieves reasonably high recall values, from 50% to 70% at low threshold points from 0 to 0.3 in all datasets. In summary, our preliminary experimental results demonstrate that our approach improves precision at lower candidate links while raising the amount of true links up to 70%. Its main limitation is that the confidence values provided by the predictive model are lower; typically, the class of true links is from 0.1 to 0.5. Therefore, at higher threshold, the number of retrieved links is very low. This is because the predictive model can effectively distinguish true and false links at low threshold, due to VSM, LSI, and LDA which achieve recall levels above 90% at lower thresholds.

IV. RELATED WORKS

Approaches combining different techniques have been proposed in the literature to improve the IR techniques and overcome their limits. For example, Chen et al. [START_REF] Chen | A combination approach for enhancing automated traceability:(NIER track)[END_REF] combine Regular Expression, Key Phrases, and Clustering algorithm K-mean to enhance the performance of VSM. Their approach has higher precision and recovers more true links than VSM alone. Cleland-Huang et al. [START_REF] Cleland-Huang | Utilizing supporting evidence to improve dynamic requirements traceability[END_REF] propose three enhancement strategies (hierarchical modelling, logical clustering of artefacts, and semi-automated pruning of the probabilistic network (PN)) to improve the performance of PN. The results indicate that these strategies effectively improve trace retrieval performance. Wang et al. [START_REF] Wang | Recovering relationships between documentation and source code based on the characteristics of software engineering[END_REF] present four strategies (source code clustering, identifier classifying, similarity thesaurus, and hierarchical structure enhancement) to improve LSI. Their approach has higher precision but lower recall. Our work differs from the above in that it combines IR techniques in order to improving their effectiveness while compensating for their weaknesses.

Our proposed approach is most related to predictive models which have been applied to identification of traceability links. For instance, Mills et al. [START_REF] Mills | A machine learning approach for determining the validity of traceability links[END_REF] use a predictive model with two features (text retrieval rankings and query quality metrics) to automatically classify links as true or false. Their approach achieves high accuracy on average using both types of features but there are still a high number of miss-classified links. Many researchers have found that unlabeled data, when used in conjunction with a small amount of labelled data, can produce considerable improvement in learning accuracy [START_REF] Zhu | Semi-supervised learning literature survey[END_REF]. The novelty of this work is that quantitative similarity measures have been considered as features to build a classification model. Our main goal is to reduce the number of false links and consequently reduce potential errors due to manual candidate links evaluation.

V. CONCLUSION

In this paper, we propose a semi-supervised method, which uses a combination of similarities measure defined by IR techniques in order to classify true links and false links. Due to unavailability of validated data training, we define a strategy to provide a small dataset. The preliminary results on four datasets indicate that our approach is more accurate on average by 3-5% than LDA and LSI and by 10% than VSM and WMD. In future work, we plan to investigate more strategies to build data training set as well as different configurations of the semi-supervised method, which could improve the performance of our approach. An ongoing validation is in progress with our industrial partners. Moreover, this approach is the first step to reach our ultimate goal, which is the maintenance of links during the project lifetime. In summary, the presented results in this paper demonstrate that semi-supervised techniques can be effectively applied to traceability links recovery.

Fig. 1 .

 1 Fig. 1. Overview of our 3 steps approach

Fig. 2 .

 2 Fig. 2. F -measure results for Icebreaker dataset

Center of Excellence for Software & Systems Traceability, http://www.coest.org/

https://radimrehurek.com/gensim/index.html threshold from 0 to 0.3 while keeping a high recall. In other words, this significantly decreases the false links at lower threshold from 0 to 0.3 ranging from 20% to

30% of the


Prithwineel Paul
email: prithwineelpaul@gmail.com

On Szilard languages of labelled insertion grammars *

Keywords: Insertion grammar, Szilard languages, Labelled insertion grammar, Chomsky hierarchy

In this work we initiate the study of Szilard languages of labelled insertion grammars. It is wellknown that there exist context-free languages which cannot be generated by any insertion grammar.

We show that there exist some regular languages which cannot be Szilard language of any labelled insertion grammar. But any regular language can be given as a homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 1. Also, any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2.

We show that even though insertion grammars of weight 1 can generate only context-free languages, there exist some context-sensitive language which can be obtained as Szilard language of a labelled insertion grammar of weight 1. At the end we show that any recursively enumerable language can be characterized by the homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 5.

Introduction

Insertion and deletion operations are well-known in formal language theory. In insertion operation, a string is inserted in the specified contexts when the insertion rule is applied, i.e., the string uv is transformed into uxv after application of the insertion rule (u, λ/x, v). Similarly, the deletion operation removes strings from the specified contexts and the string uxv is transformed into uv after application of the deletion rule (u, x/λ, v) where u and v are contexts. Ins-Del (i.e., insertion-deletion) systems work as a language generating device. These systems are powerful and with only finite set of rules and axioms can characterize recursively enumerable languages. Ins-Del systems and their variants have been investigated in [START_REF] Takahara | On the computational power of insertion-deletion systems[END_REF][START_REF] Kari | At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems, DNA Based Computers[END_REF][START_REF] Author | Recent developments on insertion-deletion systems[END_REF][START_REF] Author | Contextfree insertion-deletion systems[END_REF][START_REF] Pȃun | Representations and Characterizations of Languages in Chomsky Hierarchy by Means of Insertion-Deletion Systems, 9th International Workshop on Descriptional Complexity of Formal Systems -DCFS 2007[END_REF][START_REF] Verlan | On Minimal Context-Free Insertion-Deletion Systems[END_REF][START_REF] Kari | Contextual Insertions/Deletions and Computability[END_REF][START_REF] Krassovitskiy | Further Results on Insertion-Deletion Systems with One-Sided Contexts, Language and Automata Theory and Applications[END_REF][START_REF] Matveevici | Insertion-Deletion Systems with One-Sided Contexts[END_REF]. The study of insertion grammars (semicontextual grammars) was initiated in [START_REF] Galiukschov | Semicontextual grammars, Mathematika Logicia i Mathematika Linguistika[END_REF]. Computational power, closure properties etc. of the insertion systems have been discussed in [START_REF] Sosík | On the weight of universal insertion grammars[END_REF][START_REF] Pȃun | Representations and Characterizations of Languages in Chomsky Hierarchy by Means of Insertion-Deletion Systems, 9th International Workshop on Descriptional Complexity of Formal Systems -DCFS 2007[END_REF][START_REF] Martín | Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars[END_REF][START_REF] Pȃun | On semicontextual grammars[END_REF][START_REF] Pȃun | Two theorems about Galiukschov semicontextual languages[END_REF][START_REF] Marcus | Contextual grammars[END_REF][START_REF] Squier | Semicontextual grammars: An example[END_REF]. In [START_REF] Pȃun | DNA Computing -New Computing Paradigms[END_REF] it was proved that the linear language {a n ba n |n ≥ 1} cannot be generated by any insertion grammar. But any recursively enumerable language can be generated by insertion grammars of weight 3 when a homomorphism and weak coding is applied [START_REF] Sosík | On the weight of universal insertion grammars[END_REF][START_REF] Onodera | A note on homomorphic representation of recursively enumerable languages with insertion grammars[END_REF].

Moreover, in the study of matrix insertion grammars initiated in [START_REF] Fernau | Universal Matrix Insertion Grammars with Small Size[END_REF], it has been shown that matrix insertion grammars can even characterize recursively enumerable languages. The computational power of the insertion-deletion systems and insertion grammars combined with the parallel distributed computing models such as P systems, also have been discussed in [START_REF] Krassovitskiy | On the power of Insertion P Systems of small size[END_REF][START_REF] Alhazov | P Systems with Insertion and Deletion Exo-Operations[END_REF].

The main contribution of the paper is the association of the well-known concept of Szilard languages with insertion grammars and compare the Szilard languages obtained by these grammars with the family of languages in Chomsky hierarchy. The idea of Szilard languages is well investigated in formal language theory and their closure properties, decidability aspects, complexity aspects for Chomsky grammars, matrix grammars, parallel communicating grammar systems, communicating distributive grammar systems have been investigated in [START_REF] Mäkinen | On homomorphic images of Szilard languages[END_REF][START_REF] Cojocaru | On the Complexity of Szilard Languages of Matrix Grammars[END_REF][START_REF] Cojocaru | On some derivation mechanisms and the complexity of their Szilard languages[END_REF][START_REF] Mäkinen | On Context-Free and Szilard Languages[END_REF][START_REF] Cojocaru | The Complexity of Szilard Languages of Matrix Grammars Revisited[END_REF]. Also, the idea of derivation languages (as Szilard and Control languages) has been introduced for DNA and membrane computing models in [START_REF] Mahalingam | On Derivation Languages of a Class of Splicing Systems[END_REF][START_REF] Mahalingam | Derivation languages of Splicing P systems, BIC-TA[END_REF]. In [START_REF] Mahalingam | On Derivation Languages of a Class of Splicing Systems[END_REF],

derivation languages have been associated with splicing systems and in [START_REF] Mahalingam | Derivation languages of Splicing P systems, BIC-TA[END_REF] the same were introduced for splicing P systems.

In this work, we show that there exist some regular languages which cannot be obtained as Szilard language by any insertion grammar. But some labelled insertion grammars of weight 1 can obtain context-sensitive languages as a Szilard language. We also show that labelled insertion grammars with rules of weight 5 can characterize recursively enumerable languages when a morphism is applied and any regular language can be represented as a homomorphic image of a Szilard language obtained by labelled insertion grammar of weight 1. In [START_REF] Pȃun | On some families of Szilard languages[END_REF], it has been shown that there exist some context-free languages which cannot be represented as a homomorphic image of any context-free language. But in this paper, we show that any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2.

The paper is organized as follows. In section 2 we recall the basic definitions required for this paper along with some well-known results of insertion grammars. In section 3, we define labelled insertion grammar and the main results have been discussed in section 4. The section 5 is conclusive in nature.

Preliminaries

For the basic definitions and notions of formal language theory we refer to [START_REF] Rozenberg | Handbook of Formal Languages[END_REF]. Homomorphism: A homomorphism is a mapping h from Σ * to ∆ * where Σ, ∆ are alphabets, preserving concatenation, i.e., h(v.w) = h(v).h(w), v, w ∈ Σ * .

Chomsky normal form

Weak coding: A weak coding is a morphism which maps each letter onto a letter or empty string.

Szilard languages [START_REF] Rozenberg | Handbook of Formal Languages[END_REF]: Let G = (N, T, S, P ) be Chomsky grammar and F be an alphabet such that the cardinality of the sets F and P is same. Let f be a mapping from P to F such that for each p ∈ P a unique label f (p) is associated with p and is called the label of the rule p. A derivation in G is called successful if a string over T is generated staring from S. With each successful derivation of G, a string over F can be associated if labels of the any successful derivation are concatenated sequentially. The language generated in this manner is called Szilard language of the grammar G and is denoted by SZ(G).

Example 1. Let G = ({S}, {a, b}, S, {S → aSb, S → ab}) be a context-free grammar. The rules are labelled in the following manner: f 1 : S → aSb, f 2 : S → ab. Hence, the Szilard language obtained by the

grammar is SZ(G) = {f n 1 f 2 | n ≥ 0}.
The family of finite, linear, regular, context-free, context-sensitive and recursively enumerable languages is denoted by F IN, LIN, REG, CF, CS, RE respectively.

Insertion grammar [START_REF] Martín | Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars[END_REF]: An insertion grammar is a construct G = (V, A, P ) where V is the set of alphabets, A is the set of initial strings and P is the set of insertion rules.

Let G be an insertion grammar, then the relation ⇒ is defined in the following manner:

w ⇒ z if and only if w = w 1 uvw 2 , z = w 1 uxvw 2 for (u, λ/x, v) ∈ P, w 1 , w 2 ∈ V * .

The language generated by the insertion grammar G is:

L(G) = {z ∈ V * |w ⇒ * z, w ∈ S}.
Moreover, an insertion grammar G is called of weight n [START_REF] Sosík | On the weight of universal insertion grammars[END_REF] if and only if

n = max{|u| | (u, λ/x, v) ∈ P or (v, λ/x, u) ∈ P, x ∈ V * }.
The family of languages generated by the insertion grammars of weight n is denoted as IN S n and union of all these families is denoted as IN S ∞ .

The followings are well known results in insertion grammars [START_REF] Galiukschov | Semicontextual grammars, Mathematika Logicia i Mathematika Linguistika[END_REF][START_REF] Pȃun | On semicontextual grammars[END_REF][START_REF] Pȃun | Two theorems about Galiukschov semicontextual languages[END_REF][START_REF] Squier | Semicontextual grammars: An example[END_REF]:

(1)F IN ⊂ IN S 1 ⊂ IN S 2 ⊂ IN S 3 . . . ⊂ IN S ∞ ⊂ CS.
( (5) Each regular language is the homomorphic image of a language in IN S 1 .

The following characterization of recursively enumerable language was proved by Kari and Sosik in [START_REF] Sosík | On the weight of universal insertion grammars[END_REF] and

Onodera in [START_REF] Onodera | A note on homomorphic representation of recursively enumerable languages with insertion grammars[END_REF] independently where S 3 denotes the family of languages generated by insertion grammars of weight at most 3:

Theorem 2.1. For each recursively enumerable language L there exists a morphism h, a weak coding g and a language L 1 ∈ S 3 such that L = g(h -1 (L 1 )).

Labelled insertion grammar

A labelled insertion grammar is a construct Γ = (V 1 , A 1 , P 1 , Lab) where V 1 ∩ Lab = ∅ and the rules of P 1 are labelled in one-to-one manner with the elements from the set Lab. A derivation of insertion grammar is called a terminal derivation if it is as follows:

x 0 ⇒ a1 x 1 ⇒ a2 x 2 ⇒ a3 . . . ⇒ an x n where x 0 ∈ A 1 and no rule of Γ is applicable to x n .

If the labels of the applied insertion rules in the above terminal derivation are concatenated in the order of application, a string over Lab is obtained and the set of all such strings forms a language which is different from the language generated by the insertion grammar. It is called Szilard language of the labelled insertion grammar Γ. From the above derivation, the string a 1 a 2 . . . a n ∈ SZIN S m (Γ) where

m = max{|u| | (u, λ/α, v) ∈ P 1 or (v, λ/α, u) ∈ P 1 }.
The notation SZIN S m (Γ) denotes the Szilard language of the labelled insertion grammar Γ of weight m. The family of Szilard languages SZIN S m (Γ) of the labelled insertion grammars with insertion rules of size m, is denoted as SZIN S m . When m is not specified, it is replaced by * .

In the next section, we discuss the main results of the Szilard languages of the insertion grammars with respect to the weight. At first, we prove that there exist some regular languages which cannot be obtained as a Szilard language by any labelled insertion grammar. But any regular language can be given as homomorphic image of a Szilard language of a labelled insertion grammar of weight 1. Also, any context-free language can be given as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2. Furthermore, any recursively enumerable language can be characterized by Szilard language of the labelled insertion grammar of weight 4 when a homomorphism is applied.

The Main Results

It is very well-known that languages such as {aa} are not a Szilard language of any Chomsky grammar.

But we show that it can be Szilard language of a labelled insertion grammar.

Theorem 4.1. {aa} is a Szilard language of a labelled insertion grammar.

Proof. We construct a labelled insertion grammar Γ such that SZIN S m (Γ) = {aa}.

Let Γ = (V 1 , A 1 , R 1 ,
Lab) be a labelled insertion grammar where,

V 1 = {S, X a , Y }, T 1 = {S, Y }, A = {SY SY }, R = {a : (S, λ/X a , Y )}, Lab = {a}.
Initially only the string SY SY is present and after application of the a-rule, it is transformed into either SY SX a Y or SX a Y SY. But if the a-rule is applied once again, then the string SX a Y SX a Y is obtained. No further computation is possible. Hence, SZIN S 1 (Γ) = {aa}.

In the next theorem, we show that there exist some regular languages which cannot be obtained as Szilard language by any labelled insertion grammar.

Theorem 4.2. {a n | n ≥ 1} / ∈ SZIN S * . Proof. Suppose {a n | n ≥ 1} is Szilard language of a labelled insertion grammar Γ = (V 1 , A 1 , R 1 , Lab)
where R 1 = {a : (u, λ/k, v)} and Lab = {a}. Hence there exists a terminal derivation such that

x 0 0 ⇒ a x 0 1 . . . . (1)
where x 0 0 ∈ A 1 and the insertion rule a : (u, λ/k, v) is not applicable to x 0 1 . Similarly, the terminal derivation of the word a 2 is as follows:

x 1 0 ⇒ a x 1 1 ⇒ a x 1 2 . . . . (2)
where x 1 0 ∈ A 1 and the insertion rule a : (u, λ/k, v) is applicable to x 1 1 but not to x 1 2 . But, the x 0 0 in (1) and the x 1 0 in (2) cannot be same. Because, if (1) is true, then (2) cannot be true for x 0 0 = x 1 0 . Again, following is the terminal derivation for a 3 :

x 2 0 ⇒ a x 2 1 ⇒ a x 2 2 ⇒ a x 2 3 . . . . (3)
So, from (3) we can infer that the x 2 0 ∈ A 1 must be different from the x 0 0 in (1) and x 1 0 in (2). Hence, to obtain {a n | n ≥ 1} as Szilard language, all x i 0 (i ∈ N ∪ {0}) ∈ A 1 must be distinct. Since any derivation starts from a x i 0 ∈ A 1 , the language {a n | n ≥ 1} cannot be obtained as Szilard language by the labelled insertion grammar Γ where A 1 contains only finite number of elements.

Although {a n | n ≥ 1} cannot be the Szilard language of any labelled insertion grammar, any regular language can be represented as a homomorphic image of the Szilard language of labelled insertion grammar of weight 1.

Theorem 4.3. Any non-empty regular language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 1.

Proof. Let L be a λ-free regular language and let G = (N, T, S, P ) be a right linear grammar such that

L = L(G). Suppose N = {D 1 , D 2 , . . . , D n } where D 1 = S is the start symbol. Now we construct a labelled insertion grammar Γ such that L = L(G) = h(SZIN S 1 (Γ))
where h is a homomorphism. The rules in P are of the form D i → aD i , D i → aD j (i = j), and D i → a, D i , D j ∈ N , and a ∈ T .

Let Γ = (V 1 , A 1 , R 1 ,
Lab) be a labelled insertion grammar where

• V 1 = {X, Y, D 1 , D 2 , . . . , D n } ∪ T ; • A 1 = {XD 1 Y }; • The rules in R 1 are of the form a i k : (D i , λ/aD k , Y ) for D i → aD k , D k ∈ N, a ∈ T a i : (D i , λ/a, Y ) for D i → a, a ∈ T ; • Lab = {a i k | D i → aD k , D k ∈ N, a ∈ T } ∪ {a i | D i → a, a ∈ T }.
The non-erasing homomorphism h : (Lab) * → T * is defined as h(a i k ) = a and h(a i ) = a where a i k , a i ∈ Lab.

Every non-terminal rule (D i → aD k ) in G is simulated by an insertion rule with the label a i k and every terminal rule (D i → a) of G is associated with label a i . If the labelled insertion rules simulating the rules of a terminal derivation in G are applied in the same order, then concatenation of the labels of the insertion rules will obtain a string w 1 ∈ (Lab) * such that h(w 1 ) = w. Hence, w ∈ h(SZIN S 1 (Γ)).

For the proof of the inclusion h(SZIN S 1 (Γ)) ⊆ L(G), first assume that w ∈ h(SZIN S 1 (Γ)). Hence, there exists a terminal derivation in Γ such that h(w 1 ) = w where w 1 ∈ SZIN S 1 (Γ). If the rules in G are applied in the same order as in the terminal derivation obtaining w 1 , the string w ∈ L(G) is generated.

Hence, h(SZIN S 1 (Γ)) ⊆ L(G). This will imply, L(G) = h(SZIN S 1 (Γ)).

It has been shown in [START_REF] Martín | Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars[END_REF] that IN S 1 ⊂ CF. In fact, the linear language {a n ba n | n ≥ 1} cannot be generated by any insertion grammar [START_REF] Pȃun | DNA Computing -New Computing Paradigms[END_REF]. We show that there exists a context-sensitive language which is Szilard language of a labelled insertion grammar of weight one. Proof. We construct a labelled insertion grammar Γ which has a context-sensitive language as a Szilard language.

Let Γ = (V 1 , A 1 , R 1 , Lab) be a labelled insertion grammar where

• V 1 = {X, A, A , A , Y }; • A 1 = {XAY }; • R 1 = {a : (A, λ/A, Y ), b : (A, λ/A , A), c : (A, λ/A , A )}; • Lab = {a, b, c}.
Any computation in Γ starts from the string XAY . When the a-rule is applied, one "A" is added between A and Y . Application of the b-rule inserts A between the two A's of the string AA and hence AA A is obtained. Similarly, when the c-rule is applied, the string AA is transformed into AA A . Hence, if the labeled rules are applied in a particular order, we have

SZIN S 1 (Γ) ∩ a * b * c * = {a n b n c n | n ≥ 1}.
Since the intersection of SZIN S 1 (Γ) and the regular language a * b * c * is a context-sensitive language.

The language SZIN S 1 (Γ) must be non context-free.

Pȃun showed in [START_REF] Pȃun | On some families of Szilard languages[END_REF] that there exist context-free languages which cannot be given as a homomorphic image of Szilard language of any context-free language. Also, Theorem 4.5. [START_REF] Pȃun | On some families of Szilard languages[END_REF] The families of context-free languages and homomorphic image of the Szilard languages of the context-free languages are incomparable.

But any context-free language can be obtained as a homomorphic image of Szilard language of insertion grammar of weight 2. We show it in the following theorem.

Theorem 4.6. Any context-free language can be given as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2.

Proof. Let L be a non-empty context-free language and let G = (N, T, S, P ) be a Chomsky normal form grammar such that L = L(G). The rules in P are of the form, A → BC and A → a, where A, B, C ∈ N, a ∈ T and each rule in G is assigned with a unique label r i . Also each element of L can be obtained by initial application of the non terminal rules and then by application of the terminal rules in the leftmost manner.

We construct a labelled insertion grammar Γ

= (V 1 , A 1 , R 1 , Lab) such that L = h(SZIN S m (Γ)) where h is a morphism from Lab * to T * . The grammar Γ = (V 1 , A 1 , R 1 , Lab) is the labelled insertion grammar where • V 1 = {X, Y, E}∪N ∪T ∪∆ 1 ∪∆ 2 ∪{#, $} where ∆ 1 = {[r i ] | r i : A → BC}, ∆ 2 = {[r i ] | r i : A → a}; • A 1 = {XSEY };
• R 1 contains the following rules: For r i : A → BC:

r i : (A, λ/[r i ]BC, α 1 α 2 ) where α 1 ∈ N ∪ {E}, α 2 ∈ N ∪ {Y, E} ∪ ∆ 1 , α 1 α 2 / ∈ N {Y } ∪ {EE} ∪ {E}N ∪ {E}∆ 1 , For r i : A → a: r i a : ($A, λ/[r a ], α 1 ), α 1 ∈ N ∪ {E} and r 3 : (X, λ/#, α 2 ), α 2 ∈ N, r 4 : (α 1 α 2 , λ/$, α 3 ), α 1 ∈ {#, $}, α 2 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 3 ∈ ∆ 1 ∪ ∆ 2 ∪ N, α 1 α 2 / ∈ {#}∆ 1 ∪ {#}∆ 2 . • Lab = {r i | [r i ] ∈ ∆ 1 } ∪ {r i a | [r i ] ∈ ∆ 2 } ∪ {r 3 , r 4 }.
Finally, we define the morphism h : Lab * → T * by h(r i ) = h(r 3 ) = h(r 4 ) = λ, h(r i a ) = a where r i , r i a , r 3 , r 4 ∈ Lab and a ∈ T.

We first prove that L(G) = L ⊆ h(SZIN S 2 (Γ)). The rule r i : A → BC can be simulated by application of the r i -rule in the following manner:

Xw 1 Aw 2 Y → r i Xw 1 A[r i ]BCw 2 Y where the α 1 α 2 is
a subword of w 2 Y and the r i -rule is applicable only when α 1 α 2 satisfy the predefined conditions. The r 3 -rule transforms the word XβwEY into X#βwEY where β ∈ N, w ∈ V * 1 . The r 4 -rule inserts $ into the word X#wEY, w ∈ V + 1 to identify the leftmost non-terminal where r i a -rule can be applied. The r i : A → a rule can be simulated in the following manner:

X#w 1 $Aβ 1 w 2 Y → r i a X#w 1 $A[r a ]β 1 w 2 Y
where

β 1 ∈ N ∪ {E}, w 1 , w 2 ∈ V * 1 .
Moreover, after application of the r i a -rule, no rule will be applicable to the subword $A.

Since, any terminal string w ∈ L can be obtained by application of non-terminal rules and then by leftmost application of terminal rules, if the corresponding labelled insertion rules are applied in the same order, a terminal derivation can be obtained in Γ. In fact, a string over V 1 can be obtained where no rules further can be applied. If the labels of the applied insertion rules are concatenated in order of application, a string over Lab, say, w 1 is obtained. Application of the morphism h to w 1 , replaces each occurrence of r i , r 3 and r 4 by the empty string and r i a is replaced by a. Hence, if w ∈ L(G), then w = h(w 1 ) ∈ h(SZIN S 2 (Γ)) where w 1 ∈ SZIN S 2 (Γ).

Next we prove the inclusion h(SZIN S 2 (Γ)) ⊆ L(G) = L. Let w = h(w 1 ) where w 1 = a 1 a 2 . . . a n ∈ SZIN S 2 (Γ). If the rules in G are applied in the same order as the labelled rules in Γ, a terminal string is obtained. Moreover, after application of each r i a -rule where r i : A → a, the subword $A becomes inactive. Hence, no extra derivation is possible in Γ. Again, h(r i ) = h(r 3 ) = h(r 4 ) = λ and h(r i a ) = a, and hence, h(w 1 ) = w ∈ L(G). So, we can conclude h(SZIN S 2 (Γ)) ⊆ L(G). [START_REF] Sosík | On the weight of universal insertion grammars[END_REF] and Onodera [START_REF] Onodera | A note on homomorphic representation of recursively enumerable languages with insertion grammars[END_REF] proved that insertion grammars of weight 3 can characterize recursively enumerable languages when an inverse morphism and a weak coding is applied. Next, we show that any recursively enumerable language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 5. Moreover, we construct the insertion grammar in such a way that it simulates the derivations of G where the terminal symbols in any sentential form are generated from right to left order, i.e., in leftmost manner as in [START_REF] Sosík | On the weight of universal insertion grammars[END_REF][START_REF] Martín | Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars[END_REF]. Theorem 4.7. Each recursively enumerable language can be obtained as a homomorphic image of the Szilard language of a labelled insertion grammar of weight 5.

Kari and Sosik

Proof. Let L ∈ RE and G = (N, T, S, P ) be a grammar in Kuroda normal form such that L(G) = L. The rules of the grammar G are of the form A → BC, AB → CD, A → a, A → λ. Moreover, as in the proof of Theorem 1 in [START_REF] Martín | Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars[END_REF], we can assume that each element x ∈ L can be generated initially by application of the nonterminal rules and then by application of the terminal rules in leftmost manner. In this proof, we construct a labelled insertion grammar Γ

= (V 1 , A 1 , R 1 , Lab) such that L = h(SZIN S 5 (Γ)) where V 1 ∩ Lab = ∅.
Initially, the rules in G are labelled in one-to-one manner, i.e., each rule has a unique label r i . The set ∆ contains the labels of the rules in P . It is defined in the following manner

∆ = ∆ 1 ∪ ∆ 2 ∪ ∆ 3 ∪ ∆ 4 , where ∆ 1 = {[r i ] | r i : A → BC ∈ P }; ∆ 2 = {[r i ] | r i : AB → CD ∈ P }; ∆ 3 = {[r i ] | r i : A → a ∈ P }; ∆ 4 = {[r i ] | r i : A → λ ∈ P }; Let Γ = (V 1 , A 1 , R 1 ,
Lab) be a labelled insertion grammar, where

• V 1 = {X, Y } ∪ N ∪ {k i a |r i : A → a} ∪ {k i λ |r i : A → λ} ∪ {[r i ] | r i ∈ ∆} ∪ {[r m ]}; • A 1 = {XSY };
• R 1 contains the following rules (R 11 ) For r i : A → BC:

r 1 i : (A, λ/[r i ]BC, Y ),
r 2 i : (A, λ/[r i ]BC, α 1 Y ), α 1 ∈ N , r 3 i : (A, λ/[r i ]BC, α 1 α 2 Y ), α 1 , α 2 ∈ N , r 4 i : (A, λ/[r i ]BC, α 1 α 2 α 3 Y ), α 1 , α 2 , α 3 ∈ N , r 5 i : (A, λ/[r i ]BC, α 1 α 2 α 3 α 4 ),
where

α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 ),
r 6 i : (A, λ/[r i ]BC, α 1 α 2 α 3 α 4 α 5 ), where α 1 ∈ N, α 2 ∈ ∆ 2 , α 3 ∈ N, α 4 ∈ ∆ 1 and α 2 = α 5 .
(R 12 ) For r i : AB → CD:

r 7 i : (AB, λ/[r i ]CD, α 1 α 2 ), α 1 ∈ N, α 2 ∈ N , r 8 i : (AB, λ/[r i ]CD, Y ),
r 9 i : (AB, λ/[r i ]CD, α 1 Y ), α 1 ∈ N .
The application of the rules r 10 i , r 11 i and r 12 i in order also can simulate the rule r i : AB → CD :

r 10 i : (A, λ/[r i ], α 1 α 2 ), α 1 ∈ N, α 2 ∈ ∆ 1 ,
r 11 i : ([r i ]α 1 β 1 , λ/[r i ], α 2 α 3 ), α 1 ∈ N, α 2 ∈ N, α 3 ∈ ∆ 1 ∪ N, [r i ] ∈ ∆ 2 , β 1 ∈ ∆ 1 , r 12 i : (β 1 [r i ]B, λ/[r i ]CD, α 1 α 2 ), α 1 ∈ N, α 2 ∈ N ∪ {Y } ∪ ∆ 1 , [r i ] ∈ ∆ 2 , β 1 ∈ ∆ 1 and r 13 i : (AB, λ/[r i ]CD, α 1 α 2 α 3 α 4 α 5 ),
where

α 1 ∈ N, α 2 ∈ ∆ 2 , α 3 ∈ N, α 4 ∈ ∆ 1 and α 2 = α 5 .
(R 13 ) For r i : A → a:

a 1 i : (XA, λ/k i a , Y ), a 2 i : ([r m ]A, λ/k i a , Y ), a 3 i : ([r m ]A, λ/k i a , α 1 Y ), α 1 ∈ N , a 4 i : ([r m ]A, λ/k i a , α 1 α 2 Y ), α 1 , α 2 ∈ N , a 5 i : ([r m ]A, λ/k i a , α 1 α 2 α 3 Y ), α 1 , α 2 , α 3 ∈ N , a 6 i : ([r m ]A, λ/k i a , α 1 α 2 α 3 α 4 ),
where

α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 ),
a 7 i : ([r m ]A, λ/k i a , α 1 α 2 α 3 α 4 α 5 ),
where

α 1 ∈ N, α 2 ∈ ∆ 2 , α 3 ∈ N, α 4 ∈ ∆ 1 and α 2 = α 5 , r i m+1 : ([r m ]Ak i a , λ/[r m ], α 1 α 2 ), α 1 ∈ N, α 2 ∈ {Y } ∪ N ∪ ∆ 1 ∪ ∆ 2 .
(R 14 ) For r i : A → λ:

r 14 i : (XA, λ/k i λ , Y ),
r 15 i : ([r m ]A, λ/k i λ , Y ),
r 16 i : ([r m ]A, λ/k i λ , α 1 Y ), α 1 ∈ N , r 17 i : ([r m ]A, λ/k i λ , α 1 α 2 Y ), α 1 , α 2 ∈ N ,
r 18 i : ([r m ]A, λ/k i λ , α 1 α 2 α 3 Y ), α 1 , α 2 , α 3 ∈ N , r 19 i : ([r m ]A, λ/k i λ , α 1 α 2 α 3 α 4 ),
where

α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 ),
r 20 i : ([r m ]A, λ/k i λ , α 1 α 2 α 3 α 4 α 5 ),
where

α 1 ∈ N, α 2 ∈ ∆ 2 , α 3 ∈ N, α 4 ∈ ∆ 1 and α 2 = α 5 . r i m+2 : ([r m ]Ak i λ , λ/[r m ], α 1 α 2 ), α 1 ∈ N, α 2 ∈ {Y } ∪ N ∪ ∆ 1 ∪ ∆ 2 . (R 15 ) r m : (Xα 1 β 1 , λ/[r m ], α 2 ), α 1 , α 2 ∈ N, β 1 ∈ ∆ 1 , r m+1 : ([r m ]α 1 α 2 β 1 , λ/[r m ], α 3 ), α 1 , α 2 , α 3 ∈ N, β 1 ∈ ∆ 2 , r m+2 : ([r m ]α 1 β 1 , λ/[r m ], α 2 β 2 β 1 ), α 1 , α 2 ∈ N, β 1 ∈ ∆ 2 , β 2 ∈ ∆ 1 , r m+3 : ([r m ]α 1 β 1 , λ/[r m ], α 2 α 3 ), α 1 ∈ N, α 2 ∈ N, α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , β 1 ∈ ∆ 1 , r m+4 : ([r m ]α 1 β 1 β 2 , λ/[r m ], α 2 β 2 ), α 1 , α 2 ∈ N, β 2 ∈ ∆ 2 , β 1 ∈ ∆ 1 , r m+5 : ([r m ]α 1 β 1 β 2 , λ/[r m ], α 2 α 3 β 2 ), α 1 ∈ N, α 2 ∈ N, α 3 ∈ ∆ 1 ,β 1 ∈ ∆ 1 , β 2 ∈ ∆ 2 , r m+6 : ([r m ]α 1 β 1 , λ/[r m ], α 2 α 3 ), α 1 , α 2 ∈ N, α 3 ∈ N ∪ ∆ 1 ∪ ∆ 3 ∪ ∆ 4 , β 1 ∈ ∆ 2 . • Lab = {r 1 i , r 2 i , r 3 i , r 4 i , r 5 i , r 6 i | [r i ] ∈ ∆ 1 } ∪{r 7 i , r 8 i , r 9 i , r 10 i , r 11 i , r 12 i , r 13 i | [r i ] ∈ ∆ 2 } ∪{a 1 i , a 2 i , a 3 i , a 4 i , a 5 i , a 6 i , r i m+1 | [r i ] ∈ ∆ 3 } ∪{r 14 i , r 15 i , r 16 i , r 17 i , r 18 i , r 19 i , r 20 i , r i m+2 | [r i ] ∈ ∆ 4 }
∪{r m , r m+2 , r m+1 , r m+3 , r m+4 , r m+5 , r m+6 }.

The homomorphism h : (Lab) * → T * is defined by h(a

1 i ) = h(a 2 i ) = h(a 3 i ) = h(a 4 i ) = f (a 5 i ) = f (a 6 i ) = f (a 7
i ) = a and h(l) = λ for l ∈ Lab \ {a 1 i , a 2 i , a 3 i , a 4 i , a 5 i , a 6 i , a 7 i }. In this proof we construct an insertion grammar with labelled rules such that any recursively enumerable language can be obtained as a homomorphic image of the Szilard language of the labelled insertion grammar. Moreover, the labelled insertion grammar Γ is constructed in such a manner that each terminal derivation in G can be properly simulated by the rules in R 1 . We also show that no word except the words in L(G) can be obtained as the homomorphic image of the Szilard language of the labelled insertion grammar Γ. In this proof, the rules in (R 11 ) and (R 12 ) simulate the nonterminal rules and the rules in (R 13 ) and (R 14 ) simulate the terminal rules. The rules in (R 15 ) are constructed to simulate the leftmost derivations.

The working of the rules r i : A → BC, r i : AB → CD, r i : A → a and r i : A → λ has been discussed in the sections (I), (II), (III) and (IV) respectively.

(I) The simulation of the rule r i : A → BC in different contexts is as follows:

XwAY → r 1 i XA[r i ]BCY, w ∈ V * 1 XwAαY → r 2 i XwA[r i ]BCαY, α ∈ N, w ∈ V * 1 XwAα 1 α 2 Y → r 3 i XwA[r i ]BCα 1 α 2 Y, α 1 , α 2 ∈ N, w ∈ V * 1 XwAα 1 α 2 α 3 Y → r 4 i XwA[r i ]BCα 1 α 2 α 3 Y, α 1 , α 2 , α 3 ∈ N, w ∈ V * 1 Xw 1 Aα 1 α 2 α 3 α 4 w 2 Y → r 5 i XwA[r i ]BCα 1 α 2 α 3 α 4 Y, w 1 , w 2 ∈ V * 1 , where α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 ).
Note that after application of the rules r 1 i , r 2 i , r 3 i , r 4 i and r 5 i , the subword A[r i ] becomes inactive (i.e., no rules can be applied to A[r i ]) and becomes active once again when a word Xw

1 [r m ]A[r i ]w 2 Y, w 1 , w 2 ∈ V + 1 is obtained. The r m+3 -rule only can be applied to Xw 1 [r m ]A[r i ]w 2 Y . It has been discussed in Case 3.
(II) Simulation of the rules r i : AB → CD in different contexts:

XwABY → r 8 i XwAB[r i ]CDY, w ∈ V + 1 . . . . (1) XwABαY → r 9 i XwAB[r i ]CDαY, α ∈ N, w ∈ V + 1 . . . . (2) Xw 1 ABα 1 α 2 w 2 Y → r 7 i Xw 1 AB[r i ]CDα 1 α 2 w 2 Y, w 1 ∈ V + 1 , w 2 ∈ V * 1 , α 1 , α 2 ∈ N . . . . (3)
Similarly as above, after application of r 8 i , r 9 i and r 7 i -rule, no other rule can be applied to the subword AB[r i ]. Moreover, this subword cannot be further used for simulation of any other rule

r j : A 1 A → B 1 C 1 .
In fact, the r 7 i , r 8 i and r 9 i -rule cannot be applied to the subword

A 1 AB[r i ]CD of If a word of the form Xw 1 A 1 B 1 A[r i ]α 1 [r 1 ][r i ]α 2 [r 2 ][r i ] . . . α n [r n ][r i ] B[r i ] w 2 Y, w 1 ∈ V * 1 , w 2 ∈ V +
1 is obtained during any stage of the computation and also there exist a rule r j : A 1 B 1 → C 1 D 1 , then the application of the rule can be simulated by r 13 j -rule.

Xw 1 A 1 B 1 A[r i ]α 1 [r 1 ][r i ]α 2 [r 2 ][r i ] . . . α n [r n ][r i ]B[r i ]w 2 Y → r 13 j Xw 1 A 1 B 1 [r j ]C 1 D 1 A[r i ]α 1 [r 1 ][r i ]α 2 [r 2 ][r i ] . . . α n [r n ][r i ]B[r i ]w 2 Y.
. . . [START_REF] Author | Contextfree insertion-deletion systems[END_REF] Also, since no rule from (R 11 ), (R 12 ), (R 13 ) and (R 14 ) is applicable to the subword A 1 B 1 [r j ], it becomes inactive after the simulation. It becomes active again when the word Xw

1 [r m ] A 1 B 1 [r j ] w 2 Y, w 1 , w 2 ∈ V + 1 is obtained.
(III) Now, we discuss the Simulation of the rule r i : A → a in different contexts:

XAY → a 1 i XAk i a Y, Xw[r m ]AY → a 2 i Xw[r m ]Ak i a Y, w ∈ V + 1 , Xw[r m ]Aα 1 Y → a 3 i Xw[r m ]Ak i a α 1 Y, w ∈ V + 1 , α 1 ∈ N, Xw[r m ]Aα 1 α 2 Y → a 4 i Xw[r m ]Ak i a α 1 α 2 Y, w ∈ V + 1 , α 1 , α 2 ∈ N, Xw[r m ]Aα 1 α 2 α 3 Y → a 5 i Xw[r m ]Ak i a α 1 α 2 α 3 Y, w ∈ V + 1 , α 1 , α 2 , α 3 ∈ N, Xw[r m ]Aα 1 α 2 α 3 α 4 Y → a 6 i Xw[r m ]Ak i a α 1 α 2 α 3 α 4 Y, w ∈ V + 1 , where α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 ).
(IV) Again, the simulation of the rule r i : A → λ in different contexts is as follows:

XAY → r

∈ V + 1 , where α 1 ∈ N, α 2 ∈ N ∪ ∆ 1 , α 3 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 4 ∈ N ∪ ∆ 1 ∪ ∆ 2 , α 2 α 3 / ∈ (∆ 1 )(∆ 1 ∪ ∆ 2 ), α 3 α 4 / ∈ (∆ 1 ∪ ∆ 2 )(∆ 1 ∪ ∆ 2 )
. Now, we discuss the simulations of the leftmost derivation process in Γ in the following cases in detail.

To simulate the leftmost derivations in G, the rules in (R 15 ) are constructed. They are constructed in such a way that the symbol [r m ] identifies the leftmost non-terminal in the word XwY, w ∈ V + 1 . The working of the rules in (R 15 ) has been discussed in detail in the Case 3 to Case 6.

At first, the simulation of the leftmost derivations start with the application of the r m -rule. . . . (9)

Case 4:

x 1 ∈ Lab * , all the symbols except the symbols a 1 i , a 2 i , a 3 i , a 4 i , a 5 i , a 6 i and a 7 i for each rule r i : A → a are mapped to λ by the morphisn h. Since no extra terminal derivation is possible in Γ, the string x is obtained when the rules of the grammar G are applied in the same order. So, x ∈ L. Hence, h(SZIN S 5 (Γ)) ⊆ L(G).

Conclusion

In this work we investigated Szilard languages obtained by the labelled insertion grammars and compared them with the family of languages in Chomsky hierarchy. We showed that there exist regular languages which cannot be obtained as a Szilard language by any labelled insertion grammar. But every regular, context-free and recursively enumerable language can be obtained as a homomorphic image of the Szilard language of labelled insertion grammars with some restricted bounds. The bounds obtained in this paper are not optimal. One of the future direction of research can be to obtain the optimal bounds of these results.

  [START_REF] Rozenberg | Handbook of Formal Languages[END_REF]: For every context-free grammar G, a grammar G = (N, T, S, P ) can be effectively constructed where the rules in P are of the form A → BC and A → a such that L(G) \ {λ} = L(G ) \ {λ}.Type-0-grammar : A type-0-grammar is a construct G = (N, T, S, P ) where N is the non-terminal alphabet and T is the terminal alphabet such that N ∩ T = ∅. The starting symbol S ∈ N and the rules in P are ordered pairs (u, v) where u ∈ (N ∪ T ) * N (N ∪ T ) * and v ∈ (N ∪ T ) * . Kuroda normal form: Every type-0 grammar G = (N, T, S, P ) is in Kuroda normal form if the rules of the grammar G has one of the following forms: A → BC, AB → CD, A → a, A → λ for A, B, C, D ∈ N and a ∈ T.

Theorem 4 . 4 .

 44 CS ∩ SZIN S 1 = ∅.

14 i 15 i 16 i 17 i 18 i 19 i

 141516171819 XAk i λ Y, Xw[r m ]AY → r Xw[r m ]Ak i λ Y, w ∈ V + 1 , Xw[r m ]Aα 1 Y → r Xw[r m ]Ak i λ α 1 Y, w ∈ V + 1 , α 1 ∈ N , Xw[r m ]Aα 1 α 2 Y → r Xw[r m ]Ak i λ α 1 α 2 Y, w ∈ V + 1 , α 1 , α 2 ∈ N , Xw[r m ]Aα 1 α 2 α 3 Y → r Xw[r m ]Ak i λ α 1 α 2 α 3 Y, w ∈ V + 1 , α 1 , α 2 , α 3 ∈ N , Xw 1 [r m ]Aα 1 α 2 α 3 α 4 w 2 Y → r Xw[r m ]Ak i λ α 1 α 2 α 3 α 4 Y, w 1 , w 2

Xα[r j ]w 2 Y 8 ) 3 :

 283 → rm Xα[r j ][r m ]w 2 Y, where α ∈ N, w 2 ∈ V + 1 , [r j ] ∈ ∆ 1 . . . . (Case The subword A[r i ] in the word Xw 1 [r m ]A[r i ]w 2 Y, w 1 ∈ V + 1 , w 2 ∈ V +1 becomes active again when the subword [r m ]A[r i ] is obtained and is followed by the following step:Xw 1 [r m ]A[r i ]w 2 Y → rm+3 Xw 1 [r m ]A[r i ][r m ]w 2 Y.

  ) REG is incomparable with all families IN S n , n ≥ 1 and REG ⊂ IN S ∞ .

	(3) IN S 1 ⊂ CF but CF is incomparable with all IN S n , n ≥ 2 and IN S ∞ . Also IN S 2 contains
	non-semilinear languages.
	(4) LIN is incomparable with all IN S n , n ≥ 0 and IN S ∞ .

the word Xw

Hence, no rule in (R 12 ) is applicable to the subword AB[r i ]. So, the subword AB[r i ] becomes inactive. It becomes active once again when the word Xw 1 [r m ] AB[r i ]w 2 Y, w 1 ∈ V + 1 , w 2 ∈ V + 1 is obtained. This has been discussed futher in Case 4. In Case 1 and Case 2 we discuss the simulation of the rule r i : AB → CD in the contexts different than the contexts discussed above.

Case 1: Now, we discuss the simulation of the rule r i : AB → CD in the word

. . . (4)

Hence, the application of the r 10 -rule is followed by repeated application of the r 11 -rule and then one time application of r 12 -rule can simulate the application of the rule r i : AB → CD on the words in (4).

Moreover, the above derivations can be further extended for words Xw

l -rule is applicable to the above word

This forbids the insertion rules in (R 11 ) to be applied to the subword

Again, if there exist a rule r l : B → C D and the corresponding insertion rule in (R 11 ) is ap-

i -rule is not applicable to it. Hence, if the simulation of the rule r i : AB → CD has started, then no other rule can be applied to the subword

i , r 11 i and r 12 i -rule. Moreover, once the simulation is complete, the subword

comes inactive and will be active again when the subword [r

is obtained. We discuss about it in Case 5.

Case 2:

In this case we discuss the simulation of consecutive application of two rules in (R 12 ). The subword AB[r i ] in (II) will be activated once again after obtaining the subword

Moreover, in [START_REF] Martín | Language and Automata Theory and Applications[END_REF] after application of the r m+3 -rule only the r m+1 -rule is applicable to AB[r i ].

Case 5:

In this case we discuss how the insertion rules insert [r m ] such that the subword

1 and r i : AB → CD. At first we explain the derivation for the word Xw

Next we describe the above process for the word Xw

The above derivations can be further extended for Xw

where

In this case, the symbol [r m ] can be inserted in specified location by application of the rules with label r m+2 , r m+3 , r m+4 , r m+5 and r m+6 .

Moreover, after application of the r m+3 -rule to Xw

No insertion rule except the rules in the above derivation can be applied further to the subword

Hence, for further steps a subwords of the form

Case 6:

Now we discuss the application of the rules r 6 i , a 7 i and r 20 i where r i : AB → CD, r i : A → a, r i :

The rule r j : A 1 → a can be simulated in the following manner when the subword

Similarly, r 20 l -rule can simulate r l : A 1 → λ as in [START_REF] Cojocaru | On some derivation mechanisms and the complexity of their Szilard languages[END_REF]. Moreover, the subwords A 1 [r k ] becomes inactive. But there exist insertion rules which can be applied to [r m ]A 1 k j a and [r m ]A 1 k l λ . It has been discussed in Case 7.

Case 7:

The application of a 7 j -rule and r 20 l -rule is followed by the application of the insertion rules with label r j m+1 and r l m+2 to proceed further. Note that no other insertion rule is applicable to the subwords

Xw

In fact, the r j m+1 and r l m+2 -rule are applicable to words Xw 1 [r m ]A 1 k j a w 2 Y and Xw 1 [r m ]A 1 k l λ w 2 Y , respectively where w 1 , w 2 ∈ V + 1 . Also, no insertion rules are applicable to the subwords [r m ]A 1 k j a and [r m ]A 1 k l λ further. From the above discussions we can say that whenever the non-terminal rules are applied, corresponding labelled insertion rules in (R 11 ) and (R 12 ) can simulate it properly in the word XwY, w ∈ V + 1 . Also, the application of the rules in (R 11 ), (R 12 ), (R 13 ) and (R 14 ) , inactivates the subwords

and A[r i ] to be reactivated again by application of the rules in (R 15 ). Moreover, these subwords become active again only during the simulation of leftmost derivations by the rules in (R 13 ), (R 14 ) and (R 15 ). Hence, no extra derivation is possible in Γ. Now at first we prove the inclusion L(G) ⊆ h(SZIN S 5 (Γ)). Let w ∈ L(G). If the insertion rules in Γ are applied in the same order as in a derivation of G obtaining w, a string over V 1 is obtained where no insertion rule can be applied further. Also, if the labels of the applied rules are concatenated, a string over Lab is obtained. If the morphism h is applied to the string over Lab, then the terminal string w ∈ L(G) is obtained. Hence, L = L(G) ⊆ h(SZIN S 5 (Γ)). Now we prove the inclusion h(SZIN S 5 (Γ)) ⊆ L(G), i.e., no word except the elements of L(G) can be obtained as homomorphic image of the Szilard language of insertion grammar of weight 5.

Let x ∈ h(SZIN S 5 (Γ)). Then there exists a x 1 ∈ SZIN S 5 (Γ) such that x = h(x 1 ). The string x 1 is obtained when the labels of the rules in a terminal derivation of Γ are concatenated. In the string


Sébastien Pillet

Vincent Legrand

Mohamed Souhassou

Claude Lecomte

Kinetics of light-induced first-order phase transformation in molecular solids: Fe(btr

Kinetics of light-induced first-order phase transformation in molecular solids:

Fe"btr… 2 "NCS… The mechanism and kinetics of the thermally and light-induced spin transition of the highly cooperative spin crossover material Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O ͑btr= 4,4 Ј -bis-1,2,4-triazole͒ have been investigated by single crystal

x-ray diffraction techniques. The key role of like-spin domains is quantitatively analyzed through a nucleation, growing, and coarsening mechanism whose kinetics follow the Kolmogorov-Johnson-Mehl-Avrami model with low dimensional characteristics.

The study of structural reorganization in solids undergoing phase transformations is of fundamental importance; the nonequilibrium kinetics of such process has attracted intense research activities. Of prime interest are cases for which the phase transformation can be triggered by external stimuli ͑e.g., light, pressure͒. In this context, photoswitchable bistable molecular materials, among other spin crossover ͑SCO͒ complexes, are very promising systems exhibiting so called photoinduced phase transitions ͑PIPT͒. [START_REF]Relaxations of Excited States and Photoinduced Phase Transitions[END_REF] The nonlinearity of the light-induced processes suggests that cooperative interactions, originating from strong electron-lattice coupling, play a key role in the mechanism of PIPT. The dynamic behavior of these peculiar phase transformations is still under debate.

Evidences have been brought that universal process and scaling laws do exist for describing solid systems approaching equilibrium from a nonequilibrium state ͑e.g., thermally quenched metastable state͒. [START_REF] Kolmogorov | [END_REF] For instance, various crystallization kinetics follow the same transformation rate in reduced time units. For first-order phase transition, the transformation from the metastable phase is usually ascribed to germ nucleation of the thermodynamically stable phase followed by domain growing and coarsening. In the classical nucleation theory, nucleation and growing stages are temperature-dependent activated phenomena. Their kinetics are generally accounted for using the Kolmogorov-Johnson-Mehl-Avrami ͑KJMA͒ model, [START_REF] Kolmogorov | [END_REF] which assumes a stochastic distribution of nucleation sites, a constant nucleation rate, and linear domain growing. In this model, the fraction of transformed phase is given by X͑t͒ =1-exp͕-͓k͑ti ͔͒ n ͖. i is an incubation delay, k is the rate constant related to a characteristic transformation time k =1/ transf , and n is the Avrami exponent which reflects the degree of heterogeneity and process dimensionality. Many kinetics of phase transformations obey the KJMA rate law; it has been shown recently that this model also accounts quite well for light-induced transformations. 3,4 Iron ͑II͒ SCO complexes exhibit a molecular bistability characterized by a high spin ͑HS͒ to low spin ͑LS͒ conversion on decreasing temperature, abrupt for strongly cooperative systems. LS to HS phase switching can be reversibly triggered and controlled using appropriate optical excitation ͑LIESST phenomenon͒. The participation of like-spin domains in the spin transition behavior has been recognized from the observation of Bragg peak splitting using x-ray powder diffraction 5 and single crystal x-ray diffraction in the thermally 6 and light-induced 7 transition regimes. The structure and dynamics of like-spin domains are essential parameters in determining the use of these materials in data storage nanotechnology.

For weakly cooperative materials, the LS-HS lightinduced transformation and HS-LS relaxation kinetics follow monoexponential rates. In the case of high cooperativity, a characteristic sigmoidal curve is observed, which has been accounted for using the concept of autoacceleration. 8 A mean field master equation has been proposed for describing all the stationary and dynamic behavior, including the light-induced ones. 9 Spin transition kinetics are furthermore influenced by the degree of inhomogeneity. For instance, mechanical stressing of SCO powder samples 5 or dispersion in polymer matrices 10 result in deviation from purely exponential HS-LS relaxation rate. On the other hand, deviations from the KJMA kinetics are expected for fine grain microcrystalline powders for which growing is limited by the grain size. 11 Based on these observations, single crystal investigation techniques are preferred.

We report in this paper on the analysis of the underlying mechanism and kinetics of the thermally and light-induced phase transitions of the archetype of highly cooperative SCO complex Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O ͑btr= 4,4 Ј -bis-1,2,4-triazole͒ by temperature and time-dependent single crystal x-ray diffraction technique using a charge-coupled device ͑CCD͒ detector. Owing to its very abrupt thermal spin transitions and large hysteresis loop, we expect that domain nucleation and growing might play the key role in the transition dynamics. The crystal structure of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O consists of bidimensional extended layers connected by van der Waals interactions and hydrogen bonds. 12 This material is one of the only examples of two-dimensional ͑2D͒ polymeric SCO systems and thus deserves special attention, notably the influence of cooperativity on the spin transition kinetics. The spin transition properties 13 exhibit a 21 K hysteresis and are given in Fig. 1. A nonlinear response to photoexcitation, as well as a light-induced instability, have been pointed out by fitting the evolution under continuous optical excitation of the fraction of molecular LS species n LS ͑t͒ according to the macroscopic mean field master equation for doped Fe x M 1-x ͑btr͒ 2 ͑NCS͒ 2 •H 2 O ͑M = Co, Ni, Zn͒ polycrystalline powders. 14 Thermally induced transformation. Upon passing the thermally induced transition, the crystal lattice constants change abruptly, characteristic of first-order transition. Correlatively, the evolution of the x-ray diffraction pattern presents a splitting of the Bragg peaks, attributed to an inhomogeneous HS and LS phase coexistence ͓Fig. 2͑a͔͒, the phase transition mechanism is based on like-spin domain formation. 6 Such behavior has also been reported for other cooperative SCO materials. On the contrary, during gradual transitions, a continuous displacement of the Bragg peak 2 position occurs and linearly parallels n HS ͑t͒. 15 The isothermal evolution of the diffraction pattern of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O has also been recorded versus time following an overcooling to T = 117.2 K, slightly below the thermal HS-LS transition ͑T 1/2↓ ͒. 6 The temporal resolution of the diffraction experiment ͑ϳ10 s͒ is limited by the CCD read out time and did not allow deriving any incubation time; accordingly, i = 0 is assumed in the following. An incubation time of a few tens of seconds has been evidenced by optical absorption spectroscopy for the LS-HS photoconversion of ͓Fe͑2 -pic͒ 3 ͔Cl 2 • EtOH. 16 The integrated intensities of the Bragg peaks I͑t͒ follow a sigmoidal increasing or decreasing trend ͓Fig. 2͑b͔͒, characteristic of high cooperativity and autoaccelerated phenomenon in the Hauser formalism. 8 This nonlinear intensity evolution can be rationalized using the following domain nucleation and growing arguments. By a slight overcooling below T 1/2↓ , the system is brought in a region of the phase diagram where the LS state is thermodynamically stable. After an incubation time i , small LS clusters form via local fluctuations within the HS phase, corresponding to nucleation; LS molecular clusters of size greater than the critical size become stable nuclei. These small LS forming clusters should lead to diffuse scattering and a decrease of the Bragg peak intensity, corresponding to the HS structurally coherent matrix solely: I bragg ϳ I HS . The time scale of this phenomenon is certainly below our time resolution. Then, critical nuclei grow by incorporating neighboring molecules and gradually convert the HS phase to LS. During growing, domain sizes reach the intrinsic spatial resolution of our x-ray diffraction equipment, the transformed LS domains and the remaining HS matrix add incoherently to the total Bragg intensity signal I Bragg ϳ I HS + I LS . For this configuration, a splitting of the Bragg peaks is observed corresponding to the HS matrix and the forming LS domains, respec-tively. As the thermal HS-LS conversion proceeds, the positions in reciprocal space of the split HS and LS peaks remain unchanged; 6 the strain relaxation at the domain boundary is therefore a very local phenomenon and does not propagate to the whole crystal lattice: the nontransformed HS phase is structurally scarcely perturbed by the continuously transforming phase.

Based on the layer crystal structure of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O, the phase transformation may proceed following two low dimensional mechanisms. In the first hypothesis, nucleation and growing first quickly develop in 2D followed by a 1D slow growing perpendicular to the layers. Alternatively, the rate limiting factor could be a slow 2D growing. The integrated intensities have been converted to a time dependent dimensionless extent of phase transformation c͑t͒ = ͓I͑t͒ -I͑t → 0͔͒ / ͓I͑t → ϱ ͒ -I͑t → 0͔͒ ͓Fig. 2͑c͔͒. The KJMA model accounts well for these observed kinetics, with a characteristic time transf = 145 s ͓k = 0.0069͑1͒ s -1 ͔ and an exponent n between 2 and 3 ͓n = 2.2͑1͔͒, indicating either a deceleration of the nucleation process as more material is transformed into the stable phase ͑site saturation͒ or a low dimensional ͑2D͒ growing process. Surprisingly, common kinetics is observed for all Bragg reflections, irrespec- tive of their direction in reciprocal space. The mean field master equation 9 is usually used to quantify such spin transition kinetics and accounts well for almost all magnetic or optical measurements. These techniques measure macroscopic quantities ͑optical density and magnetic susceptibil-ity͒ directly ͑linearly in a first approximation͒ related to n HS ͑t͒, whereas our diffraction experiment is sensible to long range ordered ͑structurally coherent͒ phases; accordingly, the extent of phase transformation c͑t͒ should not be confused with the extent of molecular species HS to LS conversion ͓1-n HS ͑t͔͒.

Light-induced transformation. The LS-HS photoconversion has been performed at T = 15 K using a cw Ar-Kr laser and followed by single crystal diffraction techniques. The laser excitation wavelength ͑ = 488 nm͒ corresponds to a characteristic absorption band of the LS ground state aside the maximum of absorption to ensure a high crystal penetration depth. Under such conditions, a homogeneous nucleation is expected. A laser power threshold has been observed below which no conversion occurred ͑P limit ͒, as also discussed by Ichiyanagi et al. for Fe͑PM-Bia͒ 2 ͑NCS͒ 2 . 17 This threshold, usually attributed to a competition between the LS-HS photoexcitation and HS-LS relaxation, is reproduced within the mean field master equation approach 18 or electron lattice coupling models including long range interactions. 19 For Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O, the HS-LS relaxation rate is almost negligible at T = 15 K, the threshold should therefore result from cooperative elastic interactions solely. The eventual dependence of the transformation kinetics with laser power P ͓P limit and k͑P͔͒ needs further investigation.

The LS-HS light-induced transition exhibits additional specific features with respect to the thermally induced one. The evolution of the diffraction pattern can be separated into consecutive regimes with different characteristic times ͓Fig. 3͑a͔͒. First the molecular LS-HS conversion occurs as evidenced by the 2 displacement of the Bragg peak position ͓Fig. 3͑b͔͒, along with a splitting of the LS and HS Bragg peaks over several well separated positions ͓e.g., Fig. 3͑a͒ at t = 273 s͔. This step corresponds to the nucleation and growing process. At the end of domain growing, the single crystal consists of HS polymicrodomains with identical HS lattice constants but slightly disoriented with respect to each other ͑Fig. 3, schematic picture͒. Based on the layer crystal structure, it is more likely that the disorientation occurs perpendicular to the crystallographic a axis. Remarkably, in the late stage of the transition ͑from t = 315 s to t = 336 s͒, the separated HS Bragg peaks of lowest intensity coalesce towards the major peak; no further evolution is observed above 336 s. Final equilibrium is reached by the shrinking of the smallest size domains and a consequent growth of the major ones. Domain coarsening is therefore evidenced in spin transition materials and molecular crystals, probably due the particular layer structure and therefore highly 2D cooperativity of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O. The driving force for domain coarsening is a decrease of the interdomain boundary elastic energy. The crystal structure solved for the phototransformed phase ͑t Ͼ 336 s͒ corresponds to a pure HS state ͑n HS =1͒ with Fe-N coordination bond distances similar within 0.01 Å to the room temperature HS ones. 13 We do not observe any saturation effect ͓n HS ͑t → ϱ ͒ Ͻ 1͔ which could be attributed to a bleaching of the nucleation and a saturation of the growing process due to strong spontaneous strain induced by the large LS-HS cell volume misfit. In some special cases, the absence of observed peak splitting even for highly cooperative systems like ͓Fe͑ptz͒ 6 ͔͑BF 4 ͒ 2 , has been attributed to a hindrance of the domain growing process, 20

contrary to Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O.
The evolution of the 2 peak profile upon laser exposure has been quantitatively analyzed ͓Fig. 3͑b͔͒. The peak profiles at t =0 s ͑n HS =0͒ and t = 336 s ͑n HS =1͒ have been fitted to single Gaussian components centered at 2 LS = 12.02°and 2 HS = 11.72°, respectively. In the intermediate situations ͑0 Ͻ n HS Ͻ 1͒, the peak profiles have been described as a weighted superposition of the HS and LS components; the weights being P HS ͑t͒ and P LS ͑t͒, respectively. Based on this, the transformation kinetics can be investigated in two ways, using the 2 peak position or corresponding integrated intensity. The ratio f͑t͒ = P HS ͑t͒ / ͓P HS ͑t͒ + P LS ͑t͔͒ exhibits a clear nonlinear sigmoidal rate versus laser exposure time ͑Fig. 4͒. A least-squares fit to the KJMA model leads to n = 2.1͑1͒ and transf = 127 s ͓k = 0.0079͑2͒ s -1 ͔. On the other hand, the overall peak intensity gives information on the long range spatial coherence of the HS and LS domains. The evolution of the overall normalized peak intensity c͑t͒ = ͓I͑t͒ -I͑t → 0͔͒ / ͓I͑t → ϱ ͒ -I͑t → 0͔͒ has also been fitted to the KJMA model ͑Fig. 4͒, leading to an Avrami exponent of n = 2.1͑2͒, similar to those derived from the 2 peak position. However, the phase transformation characteristic time of transf = 205 s ͓k = 0.00488͑1͒ s -1 ͔ is clearly longer. We argue that this is due to the late stage of the transformation and domain coarsening. When the LS to HS molecular conversion is almost achieved and the crystal sample consisting of HS polydomains, the 2 peak position corresponds to 2 HS = 11.72°͓f͑t͒ϳ1͔. On the other hand, the incoherent scattering due to the intra-domain boundary and small size domains leads to a decrease of the Bragg intensity ͓c͑t͒ Ͻ 1͔. A full recovery of the final intensity occurs after the domain coarsening is achieved, that is to say when the crystal lattice has reached an equilibrium state and a single orientation.

The photomagnetic properties of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O have been analyzed and a temperature T LIESST = 61 K has been quantified. 13 Based on this T LIESST relaxation temperature, a single crystal prepared in the HS metastable state at 15 K by thermal quenching has been warmed up to 50 K, below T LIESST , and the x-ray diffraction pattern recorded versus time along the relaxation. This isothermal phase transition exhibits the splitting of the Bragg peak ͑HS and LS phase coexistence͒ but does not show any evidence for domain coarsening contrary to the light-induced transformation. It is concluded that this latter undergoes a specific mechanism. It has been recently suggested that, close to the critical temperature of the light-induced thermal hysteresis ͑LITH͒, light-induced organization of like-spin domains could occur. [START_REF] Varret | ͑private communication͒[END_REF] We could suppose that for Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O, domain coarsening is induced or at least enhanced by light excitation, even though the experiment temperature ͑15 K͒ is well below the critical temperature ͑61 K͒. By comparing the linewidth of x-ray powder diffraction pattern during light-induced and thermal transition of a Prussian blue analog, a larger domain size has been evidenced for the photoinduced phase, enlightening even more the particular light induced transformation processes. [START_REF] Hanawa | [END_REF] Our findings suggest that the first-order thermally and light-induced transitions of the SCO material Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O follow the Kolmogorov-Johnson-Mehl-Avrami model with characteristic exponent n in the range 2.0-2.5. The mechanism is of low dimensionality, in agreement with the layer crystal structure. However, no evidences have been found for a dual growing process with different characteristic time, namely 2D-layer development followed by interlayer conversion. The late time of the light-induced transition corresponds to domain coarsening of the completely converted HS state, which could be related to lightinduced organization.

This work was financially supported by the European Network of Excellence MAGMANet ͑Grant No. FP6-515767-2͒, the Université Henri Poincaré, and the CNRS. V.L. is indebted to the Ministère de l'Education Nationale, de l'Enseignement Supérieur et de la Recherche for support. We thank J. F. Létard for his help during magnetic measurements.

FIG. 1 .

 1 FIG. 1. Spin transition properties of Fe͑btr͒ 2 ͑NCS͒ 2 •H 2 O from magnetic susceptibility measurements ͑Ref. 13͒.

FIG. 3 .

 3 FIG. 3. Light-induced transformation: ͑a͒ Evolution of the diffraction pattern centered on the ͑1 3 -2͒ reflection vs time, ͑b͒ evolution of the peak intensity along 2 direction.

  . Pillet, V. Legrand, M. Souhassou, and C. Lecomte Laboratoire de Cristallographie et Modélisation des Matériaux Minéraux et Biologiques, LCM3B, UMR CNRS 7036, Université Henri Poincaré, 54506 Vandoeuvre-les-Nancy, France

2 • H 2 O S


Tom Hohweiller

Nicolas Ducros

Franc ¸oise Peyrin

Bruno Sixou

An ADMM Algorithm for Constrained Material Decomposition in Spectral CT

Keywords: Alternating direction method of multipliers, spectral computed tomography, material decomposition, nonlinear inverse problem

Thanks to photon-counting detectors, spectral computerized tomography records energy-resolved data from which the chemical composition of a sample can be recovered. This problem, referred to as material decomposition, can be formulated as a nonlinear inverse problem. In previous work, we proposed to decompose the projection images using a regularized Gauss-Newton algorithm. To reduce further the ill-posedness of the problem, we propose here to consider equality and inequality constraints that are based on physical priors. In particular, we impose the positivity of the solutions as well the total mass in each projection image. In practice, we first decompose the projection images for each projection angle independently. Then, we reconstruct the sample slices from the decomposed projection images using a standard filtered-back projection algorithm. The constrained material decomposition problem is solved by the alternating direction method of multipliers (ADMM). We compare the proposed ADMM algorithm to the unconstrained Gauss-Newton algorithm in a numerical thorax phantom. Including constraints reduces the cross-talk between materials in both the decomposed projections and the reconstructed slices.

I. INTRODUCTION

While standard computerized tomography (CT) integrates data over the X-ray spectrum, losing the energy signature of the materials, spectral CT (SPCT) keeps tracks of the energy of the detected photons. Therefore, the material composition of the sample can be recovered. There are various methods for acquiring energy-resolved data, which include the use of rapid kVp-switching, multiple source beams, multi-layer detectors [START_REF] Johnson | Dual-energy ct: general principles[END_REF], or a photon-counting detector [START_REF] Taguchi | Vision 20/20: Single photon counting x-ray detectors in medical imaging[END_REF]. The latter approach records multiple energy bins using one source beam only, which reduces the irradiation dose. SPCT is particularly interesting for imaging K-edge materials [START_REF] Cormode | Atherosclerotic plaque composition: analysis with multicolor ct and targeted gold nanoparticles 1[END_REF] (i.e., gold, iodine or gadolinium) used as contrast agents and has many potential medical applications such as neck and head cancer [START_REF] Pérez-Lara | Spectral computed tomography: Technique and applications for head and neck cancer[END_REF].

Material decomposition and tomographic reconstruction can be done jointly [START_REF] Long | Multi-material decomposition using statistical image reconstruction for spectral ct[END_REF] or sequentially, i.e., decomposing the projection images first and performing the tomographic reconstruction afterward [START_REF] Schlomka | Experimental feasibility of multi-energy photoncounting k-edge imaging in pre-clinical computed tomography[END_REF], [START_REF] Ducros | Regularization of nonlinear decomposition of spectral x-ray projection images[END_REF]. Here, we consider material This work was supported by the grant ANR-11-INBS-0006 of the French National Research Agency (ANR) and was performed within the framework of the LABEX PRIMES (ANR-11-LABX-0063). It has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement N°701915. Contact: tom.hohweiller@creatis.insa-lyon.fr decomposition in the projection domain since it allows to decompose each projection in parallel. We propose to address material decomposition as a nonlinear inverse problem. In [START_REF] Ducros | Regularization of nonlinear decomposition of spectral x-ray projection images[END_REF], we considered a Gauss-Newton algorithm to minimize a regularized cost function. This approach enjoys a fast convergence, but it does not ensure the solutions to be positive. Positivity constraints for material decomposition have been enforced in both the image [START_REF] Sidky | Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization[END_REF] and projection [START_REF] Noh | Statistical sinogram restoration in dual-energy ct for pet attenuation correction[END_REF] domains. However, these methods use first-order algorithm to minimize a cost function, thus with a low convergence rate. Our contribution here is to develop a fast constrained algorithm. In this work, we also consider equality constraints. Indeed, the quantity of injected contrast agent is known, which can improved material decomposition.

Our constrained algorithm uses the augmented Lagrangian formulation to incorporate inequality and equality constraints [START_REF] Eckstein | Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results[END_REF]- [START_REF] Ng | Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods[END_REF]. An alternating direction method of multipliers (ADMM) minimizes the Lagrangian function to recover the projected material maps. ADMM has been already used to postprocess volumes obtained afer tomographic reconstruction [START_REF] Ding | Image-domain multi-material decomposition for dual-energy ct based on correlation and sparsity of material images[END_REF] or for joint decomposition-tomographic reconstruction [START_REF]Image-domain multi-material decomposition for dual-energy ct via total nuclear norm and 0 norm[END_REF]. Both approaches considered a linearized forward model. In this work, we consider a nonlinear forward model and perform material decomposition of the projections. Our constrained algorithm is tested on realistic simulated projections of numerical thorax phantom and compared with an unconstrained Gauss-Newton algorithm.

The rest of the paper is organized as follows. Fist, we present the forward and inverse problems. Second, we describe our optimization algorithm. Then, we report and discuss some numerical experiments.

II. MATERIAL DECOMPOSITION IN SPECTRAL CT

A. Forward model

Considering a photon-counting detector with P pixels and I energy bins, the measured data is gathered in a vector s ∈ R IP . s = [s 1,1 , . . . , s I,1 , . . . , s I,P ] T

The projected mass density describes the mass of M materials on the P pixels, thus a ∈ R M P a = [a 1,1 , ..., a m,1 , ..., a M,P ] T

The standard forward model [START_REF] Schlomka | Experimental feasibility of multi-energy photoncounting k-edge imaging in pre-clinical computed tomography[END_REF], [START_REF] Ducros | Regularization of nonlinear decomposition of spectral x-ray projection images[END_REF] reads as:

s i,p = R n 0 i (E) exp - M m=1 a m,p τ m (E) dE (3)
where s i,p is the number of photons detected at the pixel p for the ith energy bin, n 0 i (E) is the effective spectrum (accounting for the incident spectrum and the detector response) at the energy E for the i-th energy bin, τ m (E) is a function representing the attenuation of the m-th material at the energy E and a m,p is the projection mass of the m-th material at pixel p, such as

a m,p = Lp ρ m (x)dx (4)
with L p is the x-ray path and ρ m (x) is the material density at the voxel x.

B. Constrained Inverse problem

For each projection angle, we propose to recover the material map a from the data s by solving the constrained optimization problem

min a C(a, s) s.t a ≥ 0 p a m,p = c m , ( 5
)
where C is the cost function and c m represents the total mass of the m-th material. Here, we assume that materials maps are positive and that the total mass of each material c m is know and constant across angles, which is a valid hypothesis when the detector field-of-view is wide enough.

To stabilize the minimization in the presence of noise, we consider

C(a, s) = D(a, s) + α R R(a) (6)
where D is the data fidelity term, R the regularization term, and α R the regularization parameter. Following [START_REF] Ducros | Regularization of nonlinear decomposition of spectral x-ray projection images[END_REF], we choose

D(a, s) = ||s -F(a)|| 2 W ( 7
)
where F represents the forward model of Eq. ( 3) and W is a diagonal weighting matrix with elements 1/ √ s. Assuming that only three materials (soft tissues, bones and gadolinium as a marker) are present in the sample, we choose

R(a) = ||∆a soft || 2 2 + ||∇a bone || 1 + ||∇a Gd || 1 (8)
where ∇ and ∆ are first-and second-order differential operator and ||.|| 2 and ||.|| 1 are the 2 -and 1 -norm, respectively.

III. CONSTRAINED MATERIAL DECOMPOSITION ADMM ALGORITHM

We propose an ADMM algorithm to solve the minimization problem described above. To this aim, we minimize the augmented Lagrangian functional

L(a, b, α α α I , α E , s) = D(a, s) + α R R(a) + H E (a, α E ) + G E (a) (9) + H I (a, b, α α α I ) + G I (a, b) + 1(b)
where H E and H I are the Lagrangian terms associated to the equality and inequality constraints, respectively, G E and G I are the augmented Lagrangian terms, 1 denotes the indicator function of the positive orthant, α E ∈ R and α α α I ∈ R M P are the Lagrangian multipliers, and b ∈ R M P is an auxiliary variable.

1) Inequality constraint: To enforce the inequality constraints, we introduce an auxiliary variable b and rewrite the constraint as

a = b (10) b ≥ 0 (11)
The constraints [START_REF] Eckstein | Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results[END_REF] and [START_REF] Wright | Numerical optimization[END_REF] translate into

H I (a, b, α α α I ) = α α α T I (b -a) (12)
G I (a, b) = β I 2 ||b -a|| 2 2 ( 13
)
whereas Eq. ( 11) is formulated with the term

1(b) = 0, if b ≥ 0 ∞, otherwise (14)
Where β I ∈ R is an augmented Lagrangian parameter.

2) Equality constraint: The equality constraints lead to

H E (a, α E ) = α E P p=1 a gd,p c gd -1 (15)
G E (a) = β E 2 P p=1 a gd,p c gd -1 2 (16)
where β E ∈ R is an augmented Lagrangian parameter. Note that the constraint applies to the gadolinium material only.

3) Minimization scheme: According to the ADMM framework, a saddle point of the augmented Lagrangian functional is obtained alternating the update of the primal variables and the Lagrangian multipliers [START_REF] Eckstein | Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results[END_REF]:

a +1 ∈ argmin a L(a, b , α E , α α α I ) (17) b +1 ∈ argmin b L(a +1 , b, α E , α α α I ) (18)
α +1 E ∈ argmax αE L(a +1 , b +1 , α E , α α α I ) (19)
α α α +1 I ∈ argmax α α αI L(a +1 , b +1 , α +1 E , α α α I ) (20)
The projected mass map a is updated using a Gauss-Newton algorithm (SPRAY toolbox [START_REF]Spray toolbox[END_REF]), the auxiliary variable b is updated using a proximal algorithm, and the Lagrangian multipliers α E and α α α I are updated with an ascent gradient algorithm [START_REF] Eckstein | Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results[END_REF]. The parameters β E and β I are increased every outer iteration with a multiplicative udpate:

β +1 E = ωβ E (21)
β +1 I = ωβ I (22)
with a positive constant ω > 1. This update rule for the Lagrangian parameter allows the algorithm to minimize in the first iterations the function C(a, s), and then after a few outer iterations the constraints since they become the predominant contribution to the Lagrangian. Denoting Π the projector operation onto the positive orthant and considering elements-wise operations, the constrained algorithm is given in Algorithm 1.

Algorithm 1: ADMM algorithm while Stopping criteria aren't met for the outer loop do while Stopping criteria aren't met for the inner loop do solve

H k δa k = -g k a k+1 = a k + λ k δa k k = k + 1 end a +1 = a k-1 b +1 = Π(a +1 - α α α I βI ) α +1 E = α E + β E H E (a +1 m ) α E α α α +1 I = α α α I + β I (b +1 -a +1 ) β +1 E = ωβ E β +1 I = ωβ I if β +1 E > β max then β +1 E = β max end if β +1 I > β max then β +1 I = β max end = + 1 end

IV. NUMERICAL EXPERIMENTS A. Phantom, simulation and decomposition parameters

In this work, a numerical phantom of a thorax is considered (240 × 185 × 84 voxels) [START_REF] Kéchichian | Shortest-path constraints for 3d multiobject semiautomatic segmentation via clustering and graph cut[END_REF]. The phantom is composed of M = 3 materials, namely soft tissues, bones and gadolinium (in the portal vein). Projections are created using the radon function of Matlab, providing 84 × 306 images. Fig. 2. Quantification error ξ θ E over all projections for the constrained algorithm (in blue) and the unconstrained algorithm (in red)

We consider a 120 kV X-Ray source, generated by the spekCalc software [START_REF] Poludniowski | Spekcalc: a program to calculate photon spectra from tungsten anode x-ray tubes[END_REF]. The photon-counting detector detect photons in I = 4 energy bins. For each pixel, 10 7 photons are send.

For both algorithms (unconstrained and constrained), the initialization is the same, with uniform materials maps a 0 m = 0 g.cm -2 for all materials. The regularization parameter is the same as well, set at α R = 1. For the unconstrained algorithm, the algorithm stops after 100 iterations to ensure the optimal solution, for a better comparison. For the ADMM algorithm the Lagrangian multipliers are initialized α 0 E = 0 and α α α 0 I = 0. The following initialisation parameters are used: β 0 E = 10 0 and β 0 I = 10 -2 , with a maximum at β max = 10 10 and an evolution parameter ω = 1.5. The algorithm stops the inner loop (update of a, Eq. ( 17)) if the relative decrease of L is small (< 10 -3 ) or if there is more than 30 iterations The decomposition are made for every degree in the range θ = [0°, 359°]. We denote a θ the decomposition for the angle θ and ρ ρ ρ z the decomposed material at a given slice z.

B. Evaluation of the methods

The constraints are evaluated by looking at the percentage of negative values, the smallest value in the projections: min(a θ m ) ∀m, θ and by computing the relative distance between the sum of the gadolinium projections and the constraint c gd :

ξ θ E = | P p=1 a θ gd,p -c gd | c gd (23)
The decomposed projections are also evaluated by computing the 2 distance between the decomposition and the ground truth:

ξ θ D = M m ||a θ m -a truth,θ m || 2 (24)
In the image domain (after the tomographic reconstruction), the 2 distance is also computed to evaluate the decomposed

χ z D = M m ||ρ ρ ρ z m -ρ ρ ρ truth,z m || 2 (25)
where ρ ρ ρ truth,z m is the reconstructed slice from the ground truth sinogram.

V. RESULTS AND DISCUSSION

A. Projection domain

Table I presents the percentage of negative values, the smallest projection value, and the smallest and highest values for ξ E for all the angles θ. The error ξ θ D and ξ θ E are displayed in Fig. 1 and Fig. 2, respectively, for all angles θ. These metrics show that the constrained algorithm gives better decomposition than the unconstrained one (by looking at the error ξ D ), and that the constraints are well satisfied for the constrained

The decomposition images are displayed in Fig. 3 for θ = 90°. The first column displays the ground truth, the second one the reconstruction obtained with the unconstrained algorithm and the third one the image obtained with the constrained algorithm (ADMM). We can see that the proposed algorithm gives visually better decomposition. Moreover, there is less bones in the gadolinium image, i.e., less cross-talk.

B. Image domain

The evolution of the error χ D is displayed on Fig. 4 as a function of the slice number z. As in the projection domain, a better decomposition is obtained with the proposed constrained algorithm. Fig. 5 displays two slices: z = 1 and z = 40. The first column shows the ground truth, the second one the slice reconstructed with unconstrained algorithm and the third one the reconstruction obtained with the constrained algorithm. The left picture, for z = 1, is a slice where there is no marker. The constrained algorithm leads to very small values whereas the unconstrained one shows some bone regions. The effect of the constrained algorithm is more clear at slice z = 40 where there is a lot of cross-talk with the unconstrained algorithm that disappears with our algorithm.

VI. CONCLUSION

We proposed an algorithm for material decomposition in SPCT. The non linear inverse ill-posed problem is solved by minimizing a cost function. Equality and inequality constraints

Fig. 1 .

 1 Fig. 1. Euclidean decomposition error ξ θ D over all projections for the constrained algorithm (in blue) and the unconstrained algorithm (in red)

  . The outer loop stops if the constraints are satisfied: ||a -b || < 10 -3 and | P p a gd,p c gd -1 | < 10 -3 for the index m = corresponding to gadolinium.

Fig. 3 .

 3 Fig. 3. Decomposition of the thorax for θ = 90°. Ground truth (first column), unconstrained algorithm (second column) and constrained (ADMM) algorithm (third column) for the 3 different materials: soft tissues (top row), bones (middle row) and gadolinium (bottom row).

Fig. 4 .

 4 Fig. 4. Euclidiean decomposition error χ sD over all slices for the constrained algorithm (in blue) and the unconstrained algorithm (in red)

TABLE I PERCENTAGE

 I OF NEGATIVE VALUES, SMALLEST VALUE, SMALLEST AND LARGEST ξ E , CONSIDERING ALL PROJECTIONS FOR BOTH ALGORITHMS.

were included in an augmented Lagrangian formulation. An ADMM algorithm was used to found its saddle point. Our new algorithm was compared with an unconstrained algorithm (a Gauss-Newton algorithm) on a numerical phantom of a thorax. Decomposition on the projections shows an improvement (qualitatively and quantitatively) of the material decomposition. Indeed, the cross-talk is reduced when the constraints are included. The improvement of the decomposition on the projection domain is maintained in the image domain after the tomographic reconstruction. Future work will address the decomposition of real data.