Luis Moreno-Jiménez
email: luis-gil.moreno-jimenez@alumni.univ-avignon.frjuan-manuel.torres@univ-avignon.fr

Juan-Manuel Torres-Moreno

Roseli Wedemann
email: roseli@ime.uerj.br

Literary Natural Language Generation with Psychological Traits

Keywords: Natural language processing, Generation of literary texts, Psychological traits

The area of Computational Creativity has received much attention in recent years. In this paper, within this framework, we propose a model for the generation of literary sentences in Spanish, which is based on statistical algorithms, shallow parsing and the automatic detection of personality features of characters of well known literary texts. We present encouraging results of the analysis of sentences generated by our methods obtained with human inspection.

Introduction

Automatic Text Generation (ATG) is a task that has been widely studied by researchers in the area of Natural Language Processing (NLP) [START_REF] Oliveira | Poetry generation with poetryme[END_REF][START_REF] Sridhara | Towards automatically generating summary comments for java methods[END_REF][START_REF] Szymanski | Hidden markov models suitable for text generation[END_REF][START_REF] Torres-Moreno | Beyond stemming and lemmatization: Ultra-stemming to improve automatic text summarization[END_REF][START_REF] Torres-Moreno | Automatic Text Summarization[END_REF]. Results from several investigations have presented very encouraging results that have allowed the establishment of progressively more challenging objectives in this field. Currently, the scope of automatic generation of text is being expanded and there is much recent work that aims at generating text related to a specific domain [START_REF] Mcroy | An augmented template-based approach to text realization[END_REF][START_REF] Molins | JSrealB: A bilingual text realizer for web programming[END_REF][START_REF] Sharples | How We Write: Writing as creative design[END_REF]. In this research scenario, algorithms have been developed, oriented to such diverse purposes as creating chat-bots for customer service in commercial applications, automatic generation of summaries for academic support, or even developing generators of literary poetry, short stories, novels, plays and essays [START_REF] Clark | Neural text generation in stories using entity representations as context[END_REF][START_REF] Riedl | Story planning as exploratory creativity: Techniques for expanding the narrative search space[END_REF][START_REF] Zhang | Chinese poetry generation with recurrent neural networks[END_REF].

The creation of a literary text is particularly interesting and challenging, when compared to other types of ATG, as these texts are not universally and perpetually perceived. Each individual has a personal conception of a literary work and perceives it in a different way. Furthermore, this perception can also Supported partially by Conacyt (Mexico) and Université d'Avignon (France).

vary depending on the reader's mood. It can thus can be assumed that literary perception is subjective and from this perspective, it is difficult to ensure that text generated by an algorithm will be perceived as literature. To reduce this possible ambiguity regarding literary perception, we consider that literature is regarded as a text that employs a vocabulary which may be largely different from that used in common language and that it employs various writing styles, such as rhymes, anaphora, etc. and figures of speech, in order to obtain an artistic, complex, possibly elegant and emotional text [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. This understanding gives us a guide for the development of our model whereby literary sentences can be generated.

We present here a model for the generation of literary text (GLT) which is guided by psychological characteristics of the personality of characters in literature. The model is based on the assumption that these psychological traits completely determine a person's speech. We thus generate literary sentences based upon a situation or context, and also on different psychological traits. For this, we have been inspired by various works which we discuss in Section 2. It is thus possible to perform an analysis of the personality of an individual through their writing, considering parts of speech such as verbs, adjectives, conjunctions, and the spinning of words or concepts, as well as other characteristics.

In Section 2, we present a review of the main literature that has addressed topics related to ATG, with focus on those that proposed methods and algorithms integrated into this work. We describe the corpus used to train our models in Section 3. Section 4 describes in detail the methodology followed for the development of our model. In Section 5, we show some experiments, as well as the results of human evaluations of the generated sentences. Finally, in Section 6 we present our conclusions.

Related Work

The task of ATG has been widely addressed by the research community in recent years. In [START_REF] Szymanski | Hidden markov models suitable for text generation[END_REF], Szymanski and Ciota presented a model based on Markov sequences for the stochastic generation of text, where the intention is to generate grammatically correct text, although without considering a context or meaning. Shridaha et al. [START_REF] Sridhara | Towards automatically generating summary comments for java methods[END_REF] present an algorithm to automatically generate descriptive summary comments for Java methods. Given the signature and body of a method, their generator identifies the content for the summary and generates natural language text that summarizes the method's overall actions.

In recent years, work has been developed for GLT, with an artistic, literary approach, as discussed in the Introduction. The works of Riedl and Young [START_REF] Riedl | Story planning as exploratory creativity: Techniques for expanding the narrative search space[END_REF] and Clark, Ji and Smith [START_REF] Clark | Neural text generation in stories using entity representations as context[END_REF] propose stochastic models, based on contextual analyzes, for the generation of fictional narratives (stories). Zhang and Lapata [START_REF] Zhang | Chinese poetry generation with recurrent neural networks[END_REF] use neural networks and Oliveira [START_REF] Oliveira | Poetryme: a versatile platform for poetry generation[END_REF][START_REF] Oliveira | Poetry generation with poetryme[END_REF] uses the technique of canned text for generating poems. Some research has achieved the difficult task of generating large texts, overcoming the barrier of phrases and paragraphs, such as the MEXICA project [START_REF] Pérez Y Pérez | Creatividad Computacional[END_REF]. MEXICA employs a computational model based on the engagement-reflection, creativity paradigm that generates narratives about pre-Columbian Aztec mythology [START_REF] Sharples | How We Write: Writing as creative design[END_REF].

Personality analysis is a complicated task that can be studied from different perspectives (see [START_REF] Wedemann | Física estadística, redes neuronales y freud[END_REF][START_REF] Siddiqui | Avalanches and generalized memory associativity in a network model for conscious and unconscious mental functioning[END_REF] and references therein). Recent research has investigated the relation between the characteristics of literary text and personality, which can be understood as the complex of the behavioural, temperamental, emotional and mental attributes that characterise a unique individual [START_REF] Mairesse | Using linguistic cues for the automatic recognition of personality in conversation and text[END_REF][START_REF] Majumder | Deep learning-based document modeling for personality detection from text[END_REF]. In [START_REF] Majumder | Deep learning-based document modeling for personality detection from text[END_REF], a type of personality is detected from the analysis of a text, using an artificial neural network (ANN), which classifies text into one of five personality classes considered by the authors (Extroversion, Neuroticism, Agreeableness, Conscientiousness, Openness). Some characteristics that are considered by the authors are writing styles and relationships between pairs of words.

Corpus

We have built two corpora in Spanish consisting of the main works of Johann Wolfgang von Goethe and Edgar Allan Poe, called cGoethe and cPoe, respectively. These corpora are analyzed and used to extract information about the vocabulary used by these authors. We later chose an important work for each author where the emotions and feelings, i.e. psychological traits, of main characters are easily perceived by readers. For Johann Wolfgang von Goethe, we have selected the novel The Sorrows of Young Werther [START_REF] Von Goethe | The Sorrows of Young Werther[END_REF] and for Edgar Allan Poe, we select the story The Cask of Amontillado [START_REF] Poe | The Cask of Amontillado[END_REF]. The two corpora generated from these literary works were used to extract the sentences, that were later used as a basis for the generation of new sentences, as we describe in section 4.1. We also use the corpora 5KL described in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF] for the final phase of the sentence generation procedure described in 4.2.

To build the cGoethe and cPoe corpora, we processed each constituent literary work (originally found in heterogeneous formats), creating a single document for each corpus, encoded in utf8. The processing of each constituent work consisted of automatically segmenting the phrases into regular expressions, using a program developed in PERL 5.0, to obtain one sentence per line in each corpus, cGoethe and cPoe.

From the segmented phrases in cGoethe and cPoe, we selected only those that belong to the works The Sorrows of Young Werther (set 1) and The Cask of Amontillado (set 2). From sets 1 and 2, we manually extracted phrases that we considered to be very literary, to form two new corpora, cWerther and cCask, respectively. In this step, we chose phrases with complex vocabulary, a directly expressed message and some literary styles like rhymes, anaphoras, etc. Table 1 shows basic statistical information of the cGoethe and cPoe corpora. Table 2, shows similar information for cWerther and cCask. Table 3 shows statistical information of the 5KL corpus. The 5KL corpus contains approximately 4 000 literary works, from various authors and different genres, and is extremely useful, as it consists of an enormous vocabulary, which forms a highly representative set to train our Word2vec based model, described in Section 4.

Model

We now describe our proposed model for the generation of literary phrases, which is an extension of Model 3 presented in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. The model consists of two phases described as follows. In the first phase, the Partially Empty Grammatical Structures (PGS), each composed by elements constituted either by parts of speech (POS) tags or function words5 , are generated. The PGS's are constructed through a morphosyntactic analysis made with FreeLing6 of the literary phrase corpora, cWerther and cCask, described in the Section 3. The POS tags of the generated PGS's are replaced by real words during the second phase.

FreeLing [START_REF] Padró | Freeling 3.0: Towards wider multilinguality[END_REF] is a commonly used tool for morphosyntactic analysis, which receives as input a string of text and returns a POS tag as output, for each word in the string. The POS tag indicates the type of word (verb, noun, adjective, adverb, etc.), and also information about inflections, i.e., gender, conjugation and number. For example, for the word "Investigador" FreeLing generates the POS tag [NCMS000]. The first letter indicates a Noun, the second a Common noun, M stands for Male gender and the fourth gives number information (Singular). The last 3 characters give information about semantics, named entities, etc. We will use only the first 4 symbols of the POS tags.

In the second phase, the POS tags in the PGS are replaced by a corresponding vocabulary, using a semantic approach algorithm based on an ANN model (Word2vec 7 ). The 5KL corpus, described in Section 3, was used for the Word2vec training, as well as the following parameters: only words with more than 5 occurrences in the 5KL corpus were considered, the context window has a dimension of 10, the dimensions of the vector representations were tested within a range of 50 to 100, being 60 the dimension with the best results. The Word2vec model used in this work is the continuous skip-gram model (Skip-gram), which receives a word (Query) as input and, as output, returns a set of words (embeddings) semantically related to the Query. The detailed process for the generation of sentences is described in what follows.

Phase I: PGS Generation

For the generation of each PGS, we use methods guided by fixed morphosyntactic structures, called Template-based Generation or Canned Text. In [START_REF] Molins | JSrealB: A bilingual text realizer for web programming[END_REF], it is argued that the use of these techniques saves time in syntactic analysis and allows one to concentrate directly on the vocabulary. The canned text technique has also been used in several works, with specific purposes, such as in [START_REF] Van Deemter | Real versus template-based natural language generation: A false opposition[END_REF][START_REF] Mcroy | An augmented template-based approach to text realization[END_REF], where the authors developed models for the generation of simple dialogues and phrases.

We use canned text to generate text based on the corpora of templates given by cWerther and cCask, described in Section 3. These corpora contain flexible grammatical structures that can be manipulated to create new phrases. The templates in a corpus can be selected randomly or through heuristics, according to a predefined objective. The process starts with the random selection of an original phrase f o ∈ corpus of length N = |f o |. A template PGS is built from the words of a sentence f o , where verbs (v), nouns (n) or adjectives (a) are replaced by their respective POS tags. Other words, particularly the function words, are retained. f o is analyzed with FreeLing to identify the content words (verbs, nouns, adjectives), so that words of f o with "values" in {v, n, a} are replaced by their respective POS tags. These content words provide most of the information in any text, regardless of their length or genre [START_REF] Bracewell | Multilingual single document keyword extraction for information retrieval[END_REF]. Our hypothesis is that by changing only these content words, we simulate the generation of phrases by homo-syntax: different semantics, same structure. The output of this process is a PGS with function words that give grammatical support and POS tags that will be replaced later, in order to change the meaning of the sentence. The general architecture of this model is illustrated in Figure 1, where full boxes represent functional words and empty boxes represent POS tags to be replaced. defined by the user (the query), while verbs and adjectives are replaced with a vocabulary closer (similar in meaning) to the original terms of the sentence. The idea is to preserve the style and emotional-psychological content, that the author intended to associate with the characters that he is portraying in his work.

The 5KL corpus is pre-processed to standardize text formatting, eliminating characters that are not important for semantic analysis such as punctuation and numbers. This stage prepares the Word2vec training data which uses a vector representation of the 5KL corpus. We use Gensim8 , a Python implementation of Word2vec. A query Q, provided by the user, is given as input to this algorithm, and its output is a set of words (embeddings) associated with a context defined by Q. In other words, Word2vec receives a term Q and returns a lexicon L(Q) = (Q 1 , Q 2 , ..., Q m ), which represents a set of m = 10 words semantically close to Q. We chose this value of m because we found that if we increase the number of words obtained by Word2vec, they start to lose their relation to Q. Formally, we represnt a mapping by Word2vec as Q → L(Q).

The authors' corpora, cGoethe or cPoe, previously analyzed using FreeLing to obtain PGS's, had a POS tag associated to each word. Now, with FreeLing, each POS tag is used to create a set of words, with the same grammatical information (identical POS tags). An Association Table (AT) is generated as a result of this process. The AT consists of k entries of the type: POS k → list of words v k,i , with same grammatical information. Formally POS k → V k = {v k,1 , v k,2 , ..., v k,i , ...}. To generate a new phrase, each tag POS k ∈ PSG, k = 1.2, ..., m, is replaced by a word selected from the lexicon V k , given by AT.

To choose a word in V k to replace POS k , we use the following algorithm. A vector is constructed for each of the three words defined as:

o: is the k th word in the phrase f o , corresponding to tag POS k ; -Q: word defining the query provided by the user; w: candidate word that could replace POS k , w ∈ V k .

For each word o, Q and w, 10 closest words o i , Q i and w i i = 1, ..., 10 are obtained with Word2vec. These 30 words are concatenated and represented by a vector U with dimension 30. The dimension was set to 30, as a compromise between lexical diversity and processing time. The vector U can be written as: U = (o 1 , ..., o 10 , Q 11 , ..., Q 20 , w 21 , ..., w 30 ) = (u 1 , u 2 , ..., u 30 ) .

(

) 1
Words o, Q and w generate three numerical vectors of 30 dimensions respectively, o → X = (x 1 , ..., x 30 ), Q → Q = (q 1 , ..., q 30 ), and w → W = (w 1 , ..., w 30 ), where the elements x j of X are obtained by taking the distance

x j = dist(o, u j ) ∈ [0, 1],
between o and each word u j ∈ U , provided by Word2vec. Obviously, the word o will be closer to the first 10 words u j than to the remaining ones. A similar process is used to obtain the values of Q and W from Q and w, respectively. Cosine similarities are then calculated between Q and W , and X and W as

θ = cos(Q, W ) = Q • W /|Q||W | , 0 ≤ θ, ≤ 1 , (2)
β = cos(X, W ) = X • W /|X||W | , 0 ≤ β, ≤ 1 . ( 3
)
This process is repeated m times, once for each word w = v k,i in V k , and similarity values θ i and β i , i = 1, ..., m, are obtained for each v k,i . Once these m similarity values are obtained, the averages θ = θ i /m and β = β i /m are calculated. The normalized ratio θ θi indicates how large the similarity θ i is with respect to the average θ that is, how close is the candidate word w = v k,i

to the query Q. The ratio βi β indicates how reduced the similarity β i is to the average β , that is, how far away the candidate word w is from word o of f o . These fractions are obtained for each pair (θ i , β i ) and combined to calculate a score Sn i as

Sn i = θ θ i • β i β . (4)
The higher the value of Sn i , the better the candidate word w = v k,i complies to the goal of approaching Q and moving away from the semantics of the original sentence. This goal aims to obtain the candidate v k,i closer to Q although still considering the context of the sentence. We use the candidate with maximum value of Sn i to replace the nouns. However, to replace verbs and adjectives, we choose the candidate with maximum Sva i , given by

Sva i = θ i θ • β β i , (5)
so as to find the candidate word v k,i closer to the meaning of the original phrase.

Finally we sort the list of values of Sn i (nouns) or Sva i (verbs and adjectives) in decreasing order and choose, at random, from the first three elements, the candidate word v k,i that will replace the POS k tag. The result is a newly generated phrase f (Q, N ) that does not exist in the corpora, but maintains the psychological mood (emotional content) of f o . The model is shown in Figure 2.

[o]

⃗ U =[ o]+[ Q ]+[ w] [w] [Q] 5KL corpus
⃗ X=dist ( ⃗ o , ⃗ U ) ⃗ W =dist ( ⃗ w , ⃗ U ) ⃗ Q=dist ( ⃗ Q , ⃗ U ) Word2vec o Nouns Adjec-Verbs max(Θ) min(β)
Author's corpora Fig. 2: Model for semantic approximation based on geometrical interpretation.

Evaluation and Results

A manual evaluation protocol has been designed to measure some characteristics of the phrases generated by our model. For baseline comparison, we used the model with the best results observed in experiments described in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. Although the baseline evaluation was done with a different scale of parameter values than in the current case, the comparison we present here helps us to understand the human evaluators' perception of the generated sentences. Sentences have been generated using the corpora 5KL, cGoethe, cPoe, cWerther and cCask, as explained in Section 4. The queries employed for generating the sentences in Spanish are Q ∈ {ODIO, AMOR, SOL, LUNA} (in English {HATE, LOVE, SUN, MOON}). We show some examples of sentences generated in Spanish in our experiments, manually translated to English.

Sentences generated using cCask, cPoe and 5KL

1. f (LOVE,12) = But I do not think anyone has ever promised against good will. 2. f (HATE,11) = A beautiful affection and an unbearable admiration took hold of me. 3. f (SUN,9) = So much does this darkness say, my noble horizon! 4. f (MOON,9) = My light is unhappy, and I wish for you.

Sentences generated using cWerther, cGoethe and 5KL

1. f (LOVE,11) = Keeping my desire, I decided to try the feeling of pleasure. 2. f (HATE,7) = I set about breaking down my distrust. 3. f (SUN,17) = He shouted, and the moon fell away with a sun that I did not try to believe. 4. f (MOON,12) = Three colors of the main shadow were still bred in this moon.

The experiment we performed consisted of generating 20 sentences for each author's corpora and the 5KL corpus. For each author, 5 phrases were generated with each of the four queries Q ∈ {LOVE, HATE, SUN,MOON}. Five people were asked to read carefully and evaluate the total of 40 sentences. All evaluators are university graduates and native Spanish speakers. They were asked to score each sentence on a scale of [0 -4], where 0 = very bad, 1 = bad, 2 = acceptable, 3 = good and 4 = very good. The following criteria were used in the evaluations.

-Grammar: spelling, correct conjugations and agreement between gender and number; -Coherence: legibility, perception of a general idea; -Context: relation between the sentence and the query.

We also asked the evaluators to indicate if, according to their own criteria, they considered the sentences as literary (0 = NOT or 1 = YES). Finally, the evaluators were to indicate which emotion they associate to each sentence (0 = Fear, 1 = Sadness, 2 = Hope, 3 = Love, and 4 = Happiness). We compared our results with the evaluation made in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF] as a baseline. The evaluated criteria are the same in that and in this work. However, the evaluation scale in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF] is in a range of [0 -2] (0 = bad, 1 = acceptable, 2 = very good). Another difference is that, for the current evaluation, we have calculated the mode instead of the arithmetic mean, since it is more feasible for the analysis of data evaluated in the Likert scale.

In Figure 3a, it can be seen that the Grammar criterion obtained good results, with a general perception of very good. This is similar to the average of 0.77 obtained in the evaluation of the model proposed in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. The Coherence was rated as bad, against the arithmetic mean of 0.60 obtained in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. In spite of being an unfavourable result, we can infer that the evaluators were expecting coherent and logical phrases. Logic is a characteristic that is not always perceived in literature and we inferred, noting that many readers considered the sentences as not being literary (Figure 3b). The evaluators perceived as acceptable the relation between the sentences and the Context given by the query. This score is similar with the average of 0.53 obtained in [START_REF] Moreno-Jiménez | Generación automática de frases literarias en español[END_REF]. Although one might consider that this rate should be improved, it is important to note that our goal in the current work is not only to approach the context, but to stay close enough to the original sentence, in order to simulate the author's style and to reproduce the psychological trait of the characters in the literary work.

In Figure 3b, we observe that 67% of the sentences were perceived as literary, although this is a very subjective opinion. This helps us understand that, despite the low rate obtained for Coherence, the evaluators do perceive distinctive elements of literature in the generated sentences. We also asked the evaluators to indicate the emotion they perceived in each sentence. We could thus measure to what extent the generated sentences maintain the author's style and the emotions that he wished to transmit. In Figure 4a, we observe that hope, happiness and sadness were the most perceived emotions in phrases generated with cCask and cPoe. Of these, we can highlight Sadness which is characteristic of much of Poe's works. Although, Hapiness is not typical in Poe's works, we may have an explanation for this perception of the readers. If we analyze The Cask of Amontillado, we observe that its main character, Fortunato, was characterized as a happy and carefree man until his murder, perhaps because of his drunkenness. The dialogues of Fortunato may have influenced the selection of the vocabulary for the generation of the sentences and the perceptions of the evaluators. In Figure 4b, we can observe that sentences generated with cWerther and cGoethe transmit mainly sadness, hope and love, which are psychological traits easily perceived when reading The Sorrows of Young Werther.

Conclusions and Future work

We have proposed a model for the generation of literary phrases, which is influenced by two important elements: a context, given by a word input by the user, and a writing mood and style, defined by the training corpora used by our models. Results are encouraging, as the model generates grammatically correct sentences. The phrases also associate well with the established context, and perceived emotions correspond, in good part, to the emotions transmitted in the literature involved. In the case of The Cask of Amontillado, the perceived emotions seem not to resemble the author's style. This may be due to the fact that, in this short story, the dialogues of the main character are happy and carefree, the tragic murder occurring only in the end. When characters in a literary text have different psychological traits, the semantic analysis of the generated phrases may show heterogeneous emotional characteristics. Experiments using works with characters showing more homogeneous psychological traits, such as The Sorrows of Young Werther, more easily detect a dominant psychological trend portrayed by the author.

Although there was a poor evaluation for the Coherence criterion, it is possible to argue that coherence is not a dominant feature of literature in general, and most of the generated sentences were perceived as literary. The model is thus capable of generating grammatically correct sentences, with a generally clear context, that transmits well the emotion and psychological traits portrayed by the content and style of an author. For future work, it is proposed to extend the length of the generated text. This could be achieved by joining several generated sentences together. In that sense, The introduction of the rhyme can be extremely interesting when produce several sentences to constitute a paragraph or a stanza. The coupling with a generator of assonant and consonant rhymes [START_REF] Medina-Urrea | Rimax: Ranking semantic rhymes by calculating definition similarity[END_REF] is planned in the near future.

4. 2 Fig. 1 :

 21 Fig. 1: Canned text model for generating a PGS.

  (a) Mode calculated from the evaluation made for the sentence generation model. (b) Perception of literary nature of sentences.

Fig. 3 :

 3 Fig. 3: Evaluation of our GLT model.

  (a) Perceived emotions in sentences generated with Allan Poe's corpora (b) Perceived emotions in sentences generated with Goethe's corpora

Fig. 4 :

 4 Fig. 4: Comparison between the emotions perceived in sentences.

Table 1 :

 1 Corpora formed by main works of each author. K represents one thousand and M represents one million.

		Sentences Tokens Characters
	cPoe	5 787	70 K	430 K
	Average for sentence	-	12	74
	cGoethe	19 519 340 K	2 M
	Average for sentence	-	17	103

Table 2 :

 2 Corpora of literary phrases of one selected work.

		Sentences Tokens Characters
	cCask	141 1 856	11 469
	Average for sentence	-	13	81
	cWerther	134 1 635	9 321
	Average for sentence	-	12	69

Table 3 :

 3 Corpus 5KL, composed of 4 839 literary works.

		Sentences Tokens Characters
	5KL	9 M 149 M	893 M
	Average for sentence	2.4 K 37.3 K

Function words (or functors) are words that have little or ambiguous meaning and express grammatical relationships among other words within a sentence, or specify the attitude or mood of the speaker, such as prepositions, pronouns, auxiliary verbs, or conjunctions.

FreeLing can be downloaded from: http://nlp.lsi.upc.edu/freeling

Word2vec is a group of related ANN models, used to produce word embeddings[START_REF] Bengio | Representation learning: A review and new perspectives[END_REF].

Available in: https://pypi.org/project/gensim/


Jacques Sakarovitch
email: sakarovitch@enst.fr

Rodrigo De Souza

ON THE DECOMPOSITION OF k-VALUED RATIONAL RELATIONS

Keywords: 1998 ACM Subject Classification: F.1.1, F.4.3 rational relation, k-valued transducer, unambiguous transducer, covering of automata

We give a new, and hopefully more easily understandable, structural proof of the decomposition of a k-valued transducer into k unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential. Moreover, this method allows further generalisation that solves the problem of decomposition of rational relations with bounded length-degree, which was left open in Weber's paper.

Introduction

This communication is part of a complete reworking 1 and rewriting of the theory of k-valued rational relations and transducers which puts it in line with the theory of rational functions (1-valued rational relations) and functional transducers and makes it appear as a natural generalisation of the latter not only at the level of the results -as we recall in the next paragraph -but also at the level of proofs.

It is decidable whether a transducer is functional (originally due to Schützenberger [START_REF] Schützenberger | Sur les relations rationnelles[END_REF]); as a consequence, the equivalence of functional transducers is decidable, and, above all, every functional transducer is equivalent to an unambiguous one [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF]. These results generalise in a remarkable way to bounded valued rational relations and transducers. It is decidable whether the image of every word by a given transducer is bounded (Weber [START_REF] Weber | On the valuedness of finite transducers[END_REF]), it is decidable whether it is bounded by a given integer k (Gurari and Ibarra [START_REF] Gurari | A note on finite-valued and finitely ambiguous transducers[END_REF]), every k-valued transducer is equivalent to the sum of k functional (and thus unambiguous) ones (Weber [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF]) and the equivalence of k-valued transducers is decidable (Culik and Karhumäki [START_REF] Culik | The equivalence of finite valued transducers (on HDT0L languages) is decidable[END_REF]).

It is noteworthy that all the results just quoted for functional transducers are now (if not in the original papers) established by means of constructions conducted on the transducers themselves [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF][START_REF] Sakarovitch | A construction on finite automata that has remained hidden[END_REF][START_REF] Sakarovitch | The rational skimming theorem[END_REF] whereas the corresponding results on k-valued transducers come, in some sense, "from outside" and, what is worse, from a different world for each of them. Gurari and Ibarra's proof for the decidability of the k-valuedness relies on a reduction to the emptiness problem for a class of counter automata, Culik and Karhumäki's one for the decidability of the equivalence appears in the context of the solution of Ehrenfeucht's conjecture on HDTOL languages, and Weber's proof of the decomposition -which we shall discuss more in detail below -is highly combinatorial and still somewhat detached from the transducers.

Our approach for those results are based on constructions which depend directly on the structure of the automata. They give back the subject a full coherence and yield systematically better complexity bounds. This will be illustrated in this paper with a new proof of the decomposition theorem which we restate below as Theorem 1.1. In [START_REF] Sakarovitch | On the decidability of finite valuedness of transducers[END_REF] we give a new proof for the decidability of the k-valuedness.

Theorem 1.1 (Weber [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF]). Every k-valued transducer T can be effectively decomposed into a sum of k (unambiguous) functional transducers. 2 Our proof for Theorem 1.1 differs from the original one by three aspects. First, Weber's proof is generally considered as very difficulty to follow, whereas ours is hopefully simpler. Second, Weber's construction results in k transducers whose number of states is a double exponential on the number of states of T , whereas we obtain a decomposition of single exponential size. Third and finally, our method allows to solve the problem, posed by Weber, of the decomposition of bounded length-degree rational relations with a more general statement (in Weber's question, θ is the length morphism): Theorem 1.2. Let τ : A * → B * be a finite image rational relation and θ : B * → C * a morphism such that the composition τ θ is k-valued. 3 Every transducer S realising τ can be effectively decomposed into k transducers whose compositions with θ are functions.

Our proof makes use twice of the notion of covering of automata. A covering of an automaton 4 A is an expansion of A: a new automaton B whose states and transitions map to those of A, preserving adjacency and labels of transitions. Moreover, the outgoing transitions of every state of B map one-to-one to those of the projection, which implies a bijection between the successful computations of A and B. Typically, B is larger than A, for several states can have the same image. This allows to choose certain subsets of the computations of A by erasing parts of B.

The two coverings we are going to define are based on a lexicographic ordering on the computations. This method can be seen as a conceptual generalisation of the one used by H. Johnson in order to build a lexicographic selection of deterministic rational relations [START_REF] Johnson | Do rational equivalence relations have regular cross-sections?[END_REF][START_REF] Johnson | Rational equivalence relations[END_REF].

The first construction, explained in Section 3. [START_REF] Béal | Conjugacy and equivalence of weighted automata and functional transducers[END_REF], is what we call the lag separation covering U N of a (real time) transducer T . It is parameterised by an integer N , and roughly speaking allows to distinguish between computations with same input and same output and 2 By "decomposed" we mean that the relation realised by T and the union of the relations realised by the k transducers are the same. 3 We write functions and relations using a postfix notation: xτ is the image of x by the relation τ and thus the composition of relations is written by left-to-right concatenation. Let us recall that the rational relations are closed under composition [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF]. 4 As we shall define in Section 2, transducers are automata of a certain kind.

whose lag5 is bounded by N . If T is k-valued, we show that for a certain N , U N contains a subtransducer V N which is equivalent to T and input-k-ambiguous6 (Proposition 4.2).

The second construction (Section 3. 2) is what we call the multi-skimming covering of an N-automaton. It proves the following multi-skimming theorem for N-rational series: Theorem 1.3. Let A be a finite N-automaton with n states realising the series s. There exists an infinite N-covering B of A such that for every integer k > 0, there exists a finite Nquotient B k of B which satisfies: B k is an N-covering of A with at most n (k + 1) n states; for every i, 0 ≤ i < k, there exists an unambiguous subautomaton

B (i) k of B k which recognises the support of s -i; there exists a subautomaton D k of B k whose behaviour is s -k.
Here sk is the series obtained from s by subtracting k to every coefficient larger than k and assigning 0 to the others. In particular, Theorem 1.3 says that, if A is a k-ambiguous automaton, then there exists a finite covering B k of A and unambiguous subautomata

B (0) k , . . . , B (k-1) k of B k such that the successful computations of the union i B (i)
k are in bijection with those of A. Of course, it is not new that sk is a N-rational series when s is. This is an old result by Schützenberger which can be proved by iterated applications of Eilenberg's Cross-Section Theorem [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF], or of the construction given in [START_REF] Sakarovitch | The rational skimming theorem[END_REF]. But all these methods yield an automaton whose size is a tower of exponentials of height k. Theorem 1.3 thus answers a problem left open in [START_REF] Sakarovitch | The rational skimming theorem[END_REF] with a solution which is better than the one that was conjectured there.

These coverings together give in two steps a decomposition of a k-valued transducer T . First, the lag separation covering of T yields a transducer V N equivalent to T and whose underlying input automaton, say A, is k-ambiguous. Next, the multi-skimming covering applied to A yields, as stated in the discussion after Theorem 1.3, k unambiguous automata B (i) k ; the successful computations of the union of the B (i) k are in bijection with those of A and, as the transitions of every B (i) k map on those of A, one can "lift" on them the output of the corresponding transitions of V N : one thus obtain k unambiguous functional transducers Z (0) , . . . , Z (k-1) decomposing T (see Figure 1).

T U N V N A i B (i) k i Z (i) π π
Figure 1: Decomposition of a k-valued transducer T . The simple edge stands for a covering; the dotted one represents an input-k-ambiguous subautomaton; the double ones are immersions; π is a projection on the underlying input automaton.

Our proof goes so to speak in the opposite way that Weber's one: our first step is to build an input-k-ambiguous transducer from which the decomposition is extracted, whereas the existence of such a transducer is viewed in [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF] as a consequence of the decomposition. Moreover, although both proofs have a very general idea in common -a classification of computations from which at most k successful ones can be distinguished, for every input word -the way we do this is completely different. Indeed, Weber's decomposition is extracted from the strongly connected components of a graph built on a preliminary decomposition of T into exponentially many functional transducers. We perform a selection among the computations of T according to a lexicographic ordering on the transitions.

A rough estimation of the complexity (number of states, as a function on the number of states of T ) of this two-step procedure gives a double exponential: one for the lag separation covering U N and other for the multi-skimming covering. However, a major feature of this construction is that every computation in the newly built automata corresponds to a computation in the original transducer -this is basically what we mean by structural proof -which allows to track down the usefulness of every newly created state. Then, a careful analysis shows that restricting the constructions to the trim parts of the automata the number of obtained states is bounded by 2 O(hLk 4 n k+4 ) states, where n is the number of states of T , h is the size of the output alphabet and L is the maximal length of the outputs of the transitions (Section 4.2). This is to be compared with the size of Weber's decomposition described in [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF], 2 2 P , where P = p(n + L + h + k) is a polynomial whose degree and coefficients do not seem to be easily derived from the arguments developed there.

The proof of Theorem 1.2 starts with the construction of k unambiguous transducers decomposing the k-valued relation τ θ. Next, we show that these transducers induce a decomposition of the set of successful computations of S. This gives a new set of k finite transducers, not necessarily unambiguous, which decompose S (Section 4.3).

Finally, let us note that -as explained in [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF] -the improvement in the size of the decomposition from double to single exponential yields an improvement of the same order for the complexity of the decision of the equivalence of k-valued transducers.

Preliminaries

We basically follow the definitions and notation in [START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Eilenberg | Automata, Languages, and Machines[END_REF][START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]. The semiring of the nonnegative integers is denoted by N, the set of words over a finite alphabet A (the free monoid over A) by A * and the empty word by 1 A * . The length of u ∈ A * is denoted by |u|. The powerset of a set X is denoted by P(X).

An automaton over a monoid M is a labelled directed graph A = (Q, M, E, I, T ) defined by the set Q of vertices, called states and E of edges, called transitions, together with two subsets I and T of Q, the initial and final states respectively. Every transition e in E is associated with a triple (p, m, q) of Q× M × Q, specifying its origin, label and end. Note that we shall explicitly consider cases where distinct transitions have the same origin, label and end, even though we take the liberty to write e : p m -→ q ∈ E meaning a transition e associated with (p, m, q). The automaton

A is finite if Q and E are finite. A computation in A is a sequence of transitions c : p 0 m 1 --→ p 1 m 2 --→ . . . m l --→ p l , also de- noted as p 0 m 1 ...m l -----→ A p l . Its label is m 1 . . . m l ∈ M and its length l. It is successful if p 0 ∈ I and p l ∈ T . The behaviour of A is the set | | |A| | | ⊆ M of
labels of successful computations. These sets are the family Rat M of the rational subsets of M .

A state of A is accessible if it can be reached by a computation starting at some state of I, and co-accessible if some state of T can be reached from it. The state is useful if is both accessible and co-accessible, and we say that A is trim if every state is useful.

If M is a free monoid A * and the labels of transitions are letters, then A is a classical automaton over A; we write in this case A = (Q, A, E, I, T ). If M is a product A * × B * , then every transition is labelled by a pair denoted as u|x and consisting of an input word u ∈ A * and an output one x ∈ B * ; and A is a transducer realising a rational relation from A * to B * . The image of a word u ∈ A * by a transducer is the set of outputs of successful computations whose input is u. The transducer is called k-valued, for k ∈ N, if the cardinality of the image of every input word is at most k.

By using classical constructions on automata, every transducer can be transformed into a real-time one: a transducer whose labels are of form a|K, where a is a letter, K ∈ Rat B * and I and T are functions from Q to Rat B * [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF][START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]. For finite image relations we may suppose that the transitions read a letter and output a single word, and the image of every final state is 1 B * . In this case, the transducer is denoted rather as T = (Q, A, B * , E, I, T ).

The underlying input automaton A of a real-time transducer T is the (classical) automaton obtained by forgetting the output of the transitions and replacing the functions I and T by their domains. The behaviour of A is the domain of the relation realised by T .

p q a | b 2 a | 1 B * a | b p q a a a
(1 A * )| | |T | | | = 1 B * and (a n )| | |T | | | = {b n , b n+1 } for n > 0.
An N-automaton is an automaton labelled by letters with multiplicities in N attached to the transitions and to initial and final states. It realises an N-rational series: a function s : A * → N which assigns to u ∈ A * a multiplicity given by summing the multiplicites (product of the multiplicities of transitions) of the successful computations labelled by u.

Every N-automaton or real-time transducer can be described by a matrix representation (λ, µ, ν), where λ ∈ S Q (ν ∈ S Q ) is a row (column) vector for the multiplicities of the initial (final) states, µ : A * → S Q×Q is a morphism, S = N for N-automata and S = Rat B * for transducers. The behaviour can be expressed by the function which maps every u ∈ A * to λ • uµ • ν. This leads to call dimension the set of states of an automaton.

It will be useful to consider N-automata whose transitions are characteristic, that is, with multiplicity 1. Every N-automaton can be transformed into such a one by splitting every transition with multiplicity l > 0 into a set of l characteristic ones (Figure 3). A morphism from B = (R, M, F, J, U ) to A = (Q, M, E, I, T ), denoted by ϕ : B → A, is a pair of mappings R → Q and F → E, both denoted by ϕ, such that Jϕ ⊆ I, U ϕ ⊆ T and for every e ∈ F , if e is associated with (p, m, q), then eϕ is associated with (pϕ, m, qϕ). We say that ϕ is a covering if ϕ induces a bijection between the outgoing transitions of p and pϕ, I is in bijection with J and T ϕ -1 = U . An immersion is by definition a subautomaton of a covering. These conditions imply that every successful computation of B maps to a A covering of the split form of an N-automaton A is the split form of an N-covering of A, see [START_REF] Béal | Conjugacy and equivalence of weighted automata and functional transducers[END_REF][START_REF] Sakarovitch | Éléments de théorie des automates[END_REF][START_REF] Sakarovitch | The rational skimming theorem[END_REF] for the definition of the latter. The N-series realised by an N-automata and any of its N-coverings are the same.

Lexicographic coverings

The idea of the two coverings we are going to define is to order lexicographically computations of automata, inasmuch as it can be done with words on some alphabet. Here, the alphabet is the set of transitions, and computations are seen as words on it.

The lexicographic ordering of computations

Let A = (Q, A, E, I, T ) be a classical automaton. Fix a (partial) ordering ≺ on E such that transitions are comparable iff they have the same label and origin. This ordering is extended on E * and thus on the computations of A in such a way that it can be called a lexicographic ordering of the computations: c = e 1 e 2 . . . e l e l+1 . . . ≺ ≺ p q q q p q q q ≺ ≺ p q q q p q q q ≺ p q b b b b

Figure 4: A lexicographic ordering between the computations of C 1 labelled by bbb and starting at p. Solid transitions are smaller than the dotted and dashed ones.

The definitions for other kinds of automata are similar but, in order to give them the wanted meaning, a little bit more delicate: for N-automata, the ordering is put on the split form, and for real-time transducers, on the underlying input automaton. 7

The multi-skimming covering of an N-automaton

The aim of the multi-skimming covering of an N-automaton A = (Q, A * , E, i, T ) is to count, for every successful computation, the number of the smaller ones according to ≺.

Let ξ : E → N Q be the function from transitions to N-vectors indexed by Q defined by (eξ) r = card {f ∈ E | f : p a -→ r and f ≺ e} , for e : p a -→ q ∈ E and r ∈ Q. Definition 3.1. The multi-skimming covering of A is the (infinite) N-automaton B of dimension Q × N Q defined as follows: 7 In order to ease the explanation, we shall describe the constructions for automata with a single initial state. Computations starting at distinct initial states become ordered by extending ≺ to new transitions i 1 -→ p starting at a "hidden" initial state i, for every p ∈ I. Initial multiplicities can be treated similarly.

• the initial state is (i, 0) (where 0 is the zero vector);

• the final states are T × N Q ; • for every (p, v) ∈ Q × N Q and every e : p a -→ q ∈ E, (p, v) a -→ (q, v • aµ + eξ) is a transition of B (where µ is the morphism of the matrix representation of A).

It follows from this definition that for every state (p, v) of B, the outgoing transitions of (p, v) are in bijection with those of p. Thus, the projection ϕ of B on the first component is an N-covering of A. The property below follows by induction on the length of computations 8 :

Property 3.2. Let C : (i, 0) u -→ B (p, v) be a computation. For every q ∈ Q, v q is the number of computations d : i u -→ A q such that d ≺ Cϕ (where Cϕ is the projection of C on A).
We define as above the (finite) automaton B k satisfying Theorem 1.3; the difference is that it counts until k -1. Let N k = {0, . . . , k -1, ω} be the quotient semiring of N given by the relation k = k + 1 (ω is the class of k and plays the role of an infinity). The dimension of B k is Q × N Q k ; transitions and initial and final states are defined as in Definition 3.1, but the matrix operations v • aµ + eξ are made in N k . The morphism N → N k induces an N-quotient B → B k , and as noted, B k is an N-covering of A. Figure 5 shows an example.

By induction on the length of computations, we have:

Property 3.3. Let C : (i, 0) u -→ B k
(p, v) be a computation. For every q ∈ Q, v q is the number of computations d : i k is defined by choosing as final only the states (p, v) ∈ T × N Q k such that q∈T v q = i; D k is the subautomaton of B k defining as final the states (p, v) ∈ T × N Q k such that q∈T v q = ω.

The lag separation covering of a real-time transducer

Let T = (Q, A, B * , E, i, T ) be a real-time transducer. We aim with the lag separation covering of T at a selection between computations of this transducer with same input and same output (stated in Property 3.9). This will be useful in Section 4 to construct a inputk-ambiguous transducer from a k-valued one.

It is not possible in general to build a finite expansion which allows to select exactly one computation for each pair of words in the relation realised by the transducer, for this would lead to an unambiguous transducer and there exist rational relations which are inherently ambiguous. The idea is to fix a parameter N and compare only computations such that the differences of lengths of outputs along them (their "lag") are bounded by N .

At first, let us recall the Lead or Delay action, defined in [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF] to describe differences of words. We restate it in a slightly different form, based on the free group F (B) generated by B: the quotient of (B ∪ B) * by the relations x x = x x = 1 B * (x ∈ B), where B a disjoint copy of B. The inverse of u ∈ B * , denoted by u, is the mirror image of u with barred letters. 8 Computations of coverings will be represented with capital letters. Intuitively, 1 • (x, y) represents the "difference" of the words x and y, being a positive word if x is a prefix of y (the lead of y with respect to x), a negative word if y is a prefix of x (the delay of y with respect to x), and 0 if x and y are not prefixes of a common word. Similarly to the multi-skimming covering, the states of the lag separation covering of T carry vectors indexed by Q. But in this case the "stored information" is the Lead or Delay between any computation and those which are smaller. Let ξ : E → P(∆) Q be the function given by (eξ) r = {(xy)ρ | f : p a|y --→ r ∈ E, f ≺ e}, for e : p a|x --→ q ∈ E and r ∈ Q. Definition 3.6. The lag separation covering of T is the (infinite) real-time transducer U = (R, A, B * , F, j, U ) defined by

B (0) 3 B (1) 3 B (2) 3 D 3 p q b a b a b a b (0 0) (1 0) (1 1) (1 2) ( 1
• R = Q×P(∆) Q ;

• j = (i, 0) (where 0 is the vector whose entries are all equal to ∅);

• U = T ×R;

• for every (p, v) ∈ R and every e :

p a|x --→ q ∈ E, (p, v) a|x --→ q, (x • v • aµ + eξ)ρ is a transition in F (
where µ is the morphism of the matrix representation of T , x • v is the vector obtained by multiplying on the left every entry of v by x, and ρ is extended componentwise to vectors in P(∆) Q ).

As before, for every state (p, v) of U, there is a bijection between the outgoing transitions of (p, v) and those of p: the projection ϕ of U on the first component is a covering on T . By induction on the length of computations, we have:

Property 3.7. Let C : (i, 0) u|x --→ (p, v) be a computation of U.
For every state q of T , v q is the set of Lead or Delay of Cϕ (the projection of C on T ) and any computation of T smaller than Cϕ and which ends in q:

v q = {LD(Cϕ, d) | d : i u|y --→ T q, d ≺ Cϕ}.
In order to build the announced selection of computations of T , we define a "bounded" lag separation covering where only the computations with lag bounded by N are compared, so that only words in ∆ N = B ≤N ∪ B ≤N are "stored" in the entries of the vectors v. Let ρ N : F (B) → ∆ N ∪ {0} be the function defined by wρ N = w, if w ∈ ∆ N , and wρ N = 0 otherwise. The element 0 is intentionally omitted from ∆ N in order to simplify the writing of Property 3.8, and in the extension of ρ N to P(F (B)) Q the image of a word not in ∆ N will be seen as the empty set so that for v ∈ P(F (B)) Q , vρ N is a vector in P(∆ N ) Q (which does not contain 0 in any of its entries). We define U N as the (finite) transducer constructed as in Definition 3.6, but with states and transitions given by:

R = Q×P(∆ N ) Q , ∀ (p, v) ∈ R, ∀ e : p a|x --→ q ∈ E (p, v) a|x --→ q, (x•v•aµ+eξ)ρ N ∈ F.
Due to the fact that ρ N is not a morphism, it is not true in general that U is a covering of U N ; but U N is another covering of T . By induction we have (see Figure 6(a)):

Property 3.8. Let C : (i, 0) u|x --→ (p, v) be a computation of U N . For every state q of T ,

v q = {LD(Cϕ, d) | d : i u|y --→ T q, x, y prefixes of a common word, d ≺ Cϕ, Cϕ, d ≤ N }.
The wanted selection is a consequence of Property 3.8 and can be stated as follows:

Property 3.9. Let V N be the subtransducer of U N obtained by removing the property of being final of every state (p, v) ∈ T × R such that 1 ∈ v t for some t ∈ T . A computation C of V N is successful if, and only if, Cϕ is successful in T and for every successful computation d of T smaller than Cϕ with (same input and) same output, Cϕ, d > N .

The transducers T and V N are equivalent: if (u, x) is in the behaviour of T , the smallest successful computation of T labelled by (u, x) is the projection of a successful one in V N .

The following remark on the trim part of V N will be useful for the evaluation of the size of the decomposition (Section 4.2). Property 3.10. Let T be a trim and k-valued transducer with n states, and whose output alphabet has h letters. The number of useful states of V N is bounded by 2 2hN k 2 n .

Proof. We write P (l) (X) for the set of the subsets with at most l elements of a set X.

Clearly, card P (l) (X) ≤ card (X) l 2 . The hypothesis that T is trim and k-valued together with Property 3.8 imply that the vectors in the useful states of V N have in every coordinate at most k words, thus these states belong to

Q × P (k) (∆ N ) Q . The cardinality of this set is at most n • card (∆ N ) k 2 n ≤ n • (2h) N k 2 n
. This is clearly bounded by 2 2hN k 2 n .

Decomposing a k-valued rational relation

As said in the introduction, we first prove a result for k-valued transducers:

Theorem 4.1. Any k-valued transducer is equivalent to an input-k-ambiguous one.

This will be established by the lag separation covering: for some adequate N , V N is input-k-ambiguous (Proposition 4.2). Next, Theorem 1.1 is proved by applying the multiskimming covering on the underlying input automaton of V N (Section 4.2).

4.1. From a k-valued transducer to an input-k-ambiguous one Proposition 4.2. Let T be a real-time transducer with n states and lengths of outputs of transitions bounded by L.

If T is k-valued, then for N ≥ L n k+1 V N is input-k-ambiguous.
The crux of the proof is a combinatorial property stated in Theorem 2.2 of [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF], and restated here as Lemma 4.3. In this lemma, T k+1 is the cartesian product of T by itself k + 1 times, a natural generalisation of the squaring of T defined in [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF] to establish the decidability of the functionality of transducers. In T 2 , every computation corresponds to a pair of computations of T with the same input; in T k+1 , every computation corresponds then to a (k+1) tuple of computations of T with the same input (this construction is heavily used in [START_REF] Sakarovitch | On the decidability of finite valuedness of transducers[END_REF] to give a new proof of the decidability of k-valuedness).

Lemma 4.3 (Weber [START_REF] Weber | Decomposing a k-valued transducer into k unambiguous ones[END_REF]). If T is k-valued, then for every successful computation c of T k+1 there exists a pair i, j of coordinates such that the projections c i and c j satisfy LD(c i , c j ) = 1 (that is, c i and c j have the same output) and c i , c j < Ln k+1 .

A concise proof for Lemma 4.3 can be derived from a property of the Lead or Delay action stated in Lemma 5 of [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF]. Although not so long, it is omitted due to space constraints.

Proof of Proposition 4.2. Fix N ≥ Ln k+1 . By Property 3.9, distinct successful computations of V N with the same input either output distinct words or have a lag greater than Ln k+1 . Hence k + 1 distinct successful computations of V N with the same input word would project on a (k + 1)-tuple of computations of T that contradicts Lemma 4.3.

Decomposing the input-k-ambiguous transducer V N

As observed in Section 3.3, T and V N are equivalent (for every N ). Thus, a decomposition of V N is also a decomposition of T .

Take N = Ln k+1 and let A be the underlying input automaton of V N . It is straightforward to decompose V N by applying the multi-skimming covering on A. By Proposition 4.2, A is k-ambiguous, hence the multi-skimming covering yields unambiguous automata B the corresponding outputs in V N of the projected ones, we obtain unambiguous transducers Z (0) , . . . , Z (k-1) whose union is equivalent to T . Figure 6 shows an example with a given ordering for each covering. Other decompositions are obtained by varying these orderings.

The number of states of the decomposition depends on the following parameters of T : n (number of states), h (cardinality of the output alphabet), L (maximal of the lengths of the outputs of transitions) and k (valuedness). We claim:

p q a | b 2 a | 1 a | b (∅ ∅) { b} ∅ ({1} {b}) { b} {1} r s a | b 2 a | b a | b a | 1 a | 1 a | b 2
(a) A lag separation covering UN with N = 1. The P(∆1) Q -vectors (vertical projection) are indexed by {p, q}, in that order. The dotted transition is larger than the solid one. The input-2-ambiguous (and equivalent to T ) subtransducer V1 is reduced to the states {r, s}. The proof is based on a fine analysis of the useful states of Z (i) and goes as follows. Let X be the set of useful states of V N (as said in Section 3.3,

Z (0) Z (1) r s a | b a | b 2 (0 0) ( 1
X ⊆ Q × P (k) (∆ N ) Q ).
Each transducer Z (i) is obtained by the multi-skimming covering of the underlying input automaton of V N , hence its states belong to X × N X k (assuming that Z (i) was built on the trim part of V N ). By the stated properties of the constructions, we can derive that if9 (P, V) is useful in Z (i) , then V has at most kn entries different from 0. In other words, the set of coordinates of V having a nonzero value belongs to P (kn) (X). There are k possible nonzero values for each such coordinate, namely {1, . . . , k -1, ω}, thus the number of useful states of Z i is at most card (X) • card P (kn) (X) • k kn . To conclude, it remains to use the discussion on the number of useful states of V N at the end of Section 3.3: we have that card P (kn) (X) ≤ card (X) (kn) 2 , and by Property 3.10, card (X) ≤ 2 2hN k 2 n . With N = n k+1 L, we obtain the bound of 2 O(hLk 4 n k+4 ) states.

The morphic decomposition theorem

We turn now to Theorem 1.2, the proof of which goes in four steps. First, we construct a k-valued transducer T realising the composition τ θ. This is done by relabelling the transitions of the transducer S realising τ : every transition p a|x --→ q of S is replaced by p a|xθ --→ q. Next, T is decomposed into k unambiguous transducers Z (0) , . . . , Z (k-1) . These transducers are immersions in V N and, by composition of morphisms, also in T ; but it may be the case that not every successful computation of T is projected by some successful one in the union of the Z (i) . The third and crucial step (described more precisely below) consists, roughly speaking, to stick the successful computations of T to the transducers Z (0) , . . . , Z (k-1) in order to obtain equivalent (thus functional) transducers W (0) , . . . , W (k-1) , not necessarily unambiguous, whose successful computations project on the whole set of successful computations of T . Finally, the transitions of each W (i) are relabelled in order to construct an immersion of S: e : p a|y --→ q in W (i) projects on a transition f of T ; the label of f is, by construction, of form a|xθ; the output y of e is replaced by x. This yields k transducers decomposing S, not necessarily functional, but whose compositions with θ are functional.

The definition of the transducers W (0) , . . . , W (k-1) is based on a generalisation of the property of functional transducers that the lag between every pair of successful computations with same label is bounded by some integer (this appears implicitly in a proof of [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF]). with same input, same output and such that c, Dϕ < K.

We can obtain each W (i) from the product of T × Z (i) by the Lead or Delay action, see [START_REF] Béal | Squaring transducers: an efficient procedure for deciding functionality and sequentiality[END_REF] for details. The part of this product restricted to states having Lead or Delay in ∆ K projects on the successful computations of T with lag smaller than K with some successful computation in Z (i) . The number of states of W (i) is bounded by n × M × card (∆ K ), where M is the number of states of Z(i). This is again of order 2 O(hLk 4 n k+4 ) .

Figure 2 :

 2 Figure 2: A 2-valued real-time transducer T over {a} * × {b} * and its (infinitely ambiguous) underlying input automaton. The behaviour of T is the relation defined by (1 A * )| | |T | | | = 1 B * and (a n )| | |T | | | = {b n , b n+1 } for n > 0.

Figure 3 :

 3 Figure 3: An N-automaton C 1 over {a, b}, on the right-hand side with characteristic transitions obtained by splitting multiplicities. If u ∈ {a, b} * is viewed as the writing in the binary system of an integer u by interpreting a as 0 and b as 1, then u| | |C 1 | | | = u.

  successful computation of A, and thus | | |B| | | ⊆ | | |A| | |. In the case of coverings, there is indeed a bijection between the successful computations and thus | | |B| | | = | | |A| | | [9].

  e n and d = e ′ 1 e ′ 2 . . . e ′ l e ′ l+1 . . . e ′ m (e i , e ′ j ∈ E for 1 ≤ i ≤ n and 1 ≤ j ≤ m) are such that c ≺ d iff c and d have the same label (thus m = n) and there exists l such that e i = e ′ i for 1 ≤ i ≤ -1 and e l ≺ e ′ l .

qProof of Theorem 1 . 3 .

 13 such that d ≺ Cϕ, if this number is smaller than k, or it is ω otherwise. In view of Property 3.3, we can obtain the subautomata B (i) k of B k by erasing the condition of being final of some final states of B k : each B (i)

  With the dashed transition starting at p being smaller than the dotted one... ... and with the other ordering on the outgoing transitions of p.

Figure 5 :Definition 3 . 4 .

 534 Figure 5: The multi-skimming covering at layer k = 3 for C 1 with two different orderings of the transitions starting at p. States of the covering are pairs (r, v), where r is a state of the automaton (horizontal projection) and v is an N 3 -vector indexed by {p, q} in that order (vertical projection). Solid transitions leaving q are smaller than the dotted ones in both coverings. The double transitions stand for four transitions. The automataB (i)3 recognising the support of s-i and D 3 recognising s -3 are given by keeping as final exactly one final state at the indicated columns.

Definition 3 . 5 .

 35 Let c : p u|x --→ q and d : p ′ u|y --→ q ′ be two computations of T with the same input u. As T is a real-time transducer, c and d have the same length. We define their Lead or Delay, denoted by LD(c, d), as the element 1 • (x, y) of ∆, and if LD(c, d) = 0, their lag as the integer c, d = max{|LD(c ′ , d ′ )| | c ′ , d ′ prefixes of c, d with the same length}.

  in A, and whose successful computations are in bijection with those of A. By lifting to the transitions of B

0) a | b a | b 2 (

 2 b) The lifted transducers Z (0) and Z (1) from a 2-skimming of the input automaton of V1. The choices of final states yield | | |Z (0) | | | : a n → b n (n ≥ 0) and | | |Z (1) | | | : a n → b n+1 (n > 0).

Figure 6 :Property 4 . 4 .

 644 Figure 6: A decomposition of the 2-valued transducer T of Figure 2. Property 4.4. Each transducer Z (i) has at most 2 O(hLk 4 n k+4 ) useful states.

Property 4 . 5 .

 45 Let N = n k+1 L and K = 2(k + 1)N . If T is k-valued, then for every successful computation c of T there exists a successful computation D in Z (0) ∪ • • • ∪ Z (k-1)

To be defined in the body of the paper.

When it comes to ambiguity in transducers, we distinguish between input-ambiguity (called ambiguity in most of the references) and ambiguity of the transducer (which allows to define ambiguity for relations).

Capital letters are used in order to distinguish the states of Z (i) from the states of other automata.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

support of CAPES Foundation (Brazilian government) for doctoral studies is gratefully acknowledged by the second author (second in the alphabetical order, as in use in the British and French encyclopedias -not in the Lusitanian ones).


C L Bassani

J M Herri

A K Sum

R E M Morales
email: rmorales@utfpr.edu.br

A Cameirão
email: cameirao@emse.fr

A Growth Model of Gas Hydrates in Water-in-Oil Emulsion Flow

Keywords: gas hydrates, flow assurance, crystal growth

The correct prediction of gas hydrate formation is important to estimate pipeline blockage (plugging) in oil and gas production operations. This study presents a revisited model for growth of gas hydrates in water-in-oil emulsion flow. Literature points out that hydrates form as shells around the water droplets. The water core shrinkage rate (inward growth) is related to gas diffusion through the hydrate shell, while water permeation through the hydrate shell is the limiting phenomenon for outward growth. The models of literature are herein corrected (consideration of gas solubility in the hydrate shell, consideration of gas concentration along the shell coupled with gas consumption in the outer surface, coupling between gas absorption by the bulk and gas consumption due to hydrate formation) and extended for considering the crystal integration process in the outer particle surface and the mass transfer between the particle and the bulk. The model is compared to experimental data and the trend of the gas consumption over time due to hydrate formation is validated.

Introduction

The high pressure and low temperature conditions commonly found in offshore oil & gas production scenarios favor the formation of gas hydrates. Gas hydrates are crystals formed by the imprisonment of gas molecules (e.g., light hydrocarbons) in cages formed of hydrogenbonded water molecules [START_REF] Sloan | Clathrate hydrates of natural gases, 3rd ed[END_REF]. This crystal grows and agglomerates as it flows along the pipeline, causing eventual blocks with related production stop and revenue losses.

Gas hydrates form as shells contouring water droplets in the case of water-in-oil emulsion flow [START_REF] Sloan | Natural gas hydrates in flow assurance[END_REF]. This hydrate shell is related to gas diffusion and water permeation resistances for the crystal growth kinetics [START_REF] Turner | Methane hydrate formation and an inward growing shell model in water-in-oil dispersions[END_REF][START_REF] Shi | An inward and outward natural gas hydrates growth shell model considering intrinsic kinetics, mass and heat transfer[END_REF]. The hydrate formation rate, by its turn, is related to the gas consumption rate along the pipeline, which cause flow deceleration [START_REF] Bassani | A three-phase solid-liquid-gas slug flow mechanistic model coupling hydrate dispersion formation with heat and mass transfer[END_REF], promoting settling of the slurry [START_REF] Bassani | Hydrate formation effects on slug flow hydrodynamics and heat transfer: wall deposition vs. dispersion formation, in: IV Journeys Multiph. Flows, JEM-2017-0015[END_REF] once the deposition critical velocity is reached [START_REF] Peker | Solid-liquid two-phase flow[END_REF]. Several growth kinetic models have been proposed in literature to estimate the gas hydrate formation rate (see Ribeiro Jr and Lage [START_REF] Ribeiro | Modelling of hydrate formation kinetics: State-of-the-art and future directions[END_REF] and Yin et al. [START_REF] Yin | Review of gas hydrate dissociation kinetic models for energy recovery[END_REF] for a compilation of kinetic models), but predictive models for gasoil-water systems are yet scarce [START_REF] Turner | Methane hydrate formation and an inward growing shell model in water-in-oil dispersions[END_REF][START_REF] Shi | An inward and outward natural gas hydrates growth shell model considering intrinsic kinetics, mass and heat transfer[END_REF].

The present study extends the models of Turner et al. [START_REF] Turner | Methane hydrate formation and an inward growing shell model in water-in-oil dispersions[END_REF] and Shi et al. [START_REF] Shi | An inward and outward natural gas hydrates growth shell model considering intrinsic kinetics, mass and heat transfer[END_REF] considering: (i) the gas solubility in the hydrate shell; (ii) the crystal integration in the outer surface of the particle; (iii) the competition between gas absorption from the free gas phase by the bulk and the gas depletion due to hydrate formation as proposed in [START_REF] Englezos | Kinetics of formation of methane and ethane gas hydrates[END_REF][START_REF] Herri | Methane hydrate crystallization mechanism from insitu particle sizing[END_REF]; and (iv) the mass transfer between the particle and the bulk [START_REF] Herri | Methane hydrate crystallization mechanism from insitu particle sizing[END_REF].

Mathematical model

Water is considered flowing as an emulsion, i.e., small and spherical droplets homogeneously distributed in oil continuous phase [START_REF] Brauner | The prediction of dispersed flows boundaries in liquid-liquid and gas-liquid systems[END_REF]. In this kind of system and whenever pressure and temperature conditions are favorable, gas hydrates form as a shell around the water droplets [START_REF] Sloan | Natural gas hydrates in flow assurance[END_REF], as depicted in Fig. 1(a). The main phenomena associated to growth kinetics of this kind of particle is presented in Fig. 1(b-g). Gas is absorbed by the bulk while it depletes in gas as hydrates form (b). Inner growth is related to gas diffusion through the hydrate shell (d), which also competes with mass transfer between the particle and the bulk (c) and crystal integration process in the inner surface (e). The core shrinkage makes water from the core to be expulsed through the hydrate porous shell (f), thus turning possible crystal integration in the outer surface to happen (g), with consequent outer growth. The gas concentration along the hydrate shell is calculated by Fick's Law in spherical coordinates, Eq. (1) (nomenclature section at the end of the article). The boundary conditions are the crystal integration in the inner surface of the particle and the mass transfer between the particle and the bulk in the outer surface, Eq. ( 2). The ODE solution is shown in Eq. (3).

,, The gas molar flux through the hydrate shell equals the amount of gas consumed to form hydrates in the inner growth and comes from derivation of Eq. ( 3), as shown in Eq. ( 4) (left). Yet knowing that hydrate formation follows the (pseudo)-stoichiometry of

in in h rr h h in i i in i eq w rr C dC D A k A f dr H           ; , ,, out out h rr gi h h out i m out i b h rr out C dn dC D A h A C dr S dt           (2)   2 , 2 22 1 1 1 1 4 1 1 1 1 wh gi in i in h h eq h b eq m out h h w h out in out m i out in HD dn r r k r S C C S C C h dt r S D H D r r h k rr                         with eq w eq C H f  (3)
  2 11 G H O Hyd    
, where  is the hydration number, then the hydrate formation is related to the gas consumption rate, Eq. ( 4) (right). Therefore, the linear growth rate of the inner surface of the particle in dr dt  is related to the molar hydrate formation rate as shown in Eq. ( 5).  

1 g h in in dn dn dt dt         (4)
, [START_REF] Turner | Methane hydrate formation and an inward growing shell model in water-in-oil dispersions[END_REF] 4

3 hi h in h in dn d r dt M dt            , 2 22 2 1 4 1 11 gi h h b eq m out out in h h in w h in h in out i m out dn S S C C h r dt dr M dt r H S r D r r k h r                       (5)
Outward growth is limited to water availability in the outer surface. Considering a fully rigid shell with no head loss in the capillaries, the water volumetric flowrate through the hydrate shell is the difference between the core volume shrinkage and the amount of water consumed to form hydrates, which are related to the inner growth rate as shown in Eq. ( 6). At maximum, all the permeated water will convert into hydrates instantly in the particle outer surface; but if enough water arrives at the particle outer surface, then crystal integration process may limit outer growth, Eq. ( 7). The linear outer growth rate is expressed in Eq. [START_REF] Ribeiro | Modelling of hydrate formation kinetics: State-of-the-art and future directions[END_REF].

core w in dd Q dt dt               2 41 1 w h in in hw M dr Qr M dt               (6)
The hydrate formation rate of the entire particle population is estimated by Eq. ( 9). The gas concentration in the bulk comes from a mass balance between the gas absorbed by the bulk and the gas consumed due to hydrate formation [START_REF] Englezos | Kinetics of formation of methane and ethane gas hydrates[END_REF][START_REF] Herri | Methane hydrate crystallization mechanism from insitu particle sizing[END_REF], Eq. [START_REF] Englezos | Kinetics of formation of methane and ethane gas hydrates[END_REF]

              ( 10
)
The model is composed of three ODEs for the inner growth rate (Eq. ( 5)), the outer growth rate (Eq. ( 8)) and the bulk concentration (Eq. ( 10)). This system of ODEs is solved by Runge-Kutta method of 4 th order. As initial conditions, the bulk is considered saturated and the inner and outer radius are considered equal to the droplet radius. The water permeation rate, Eq. ( 6), is evaluated explicitly and has initial value of zero. All particles are considered to be equal and agglomeration is neglected; thence, the sum term of Eq. ( 10) becomes a multiplication by the number of particles i in the system.

Results and Discussions

The model is compared with experimental results from Melchuna et al. [START_REF] Melchuna | Topological modeling of methane hydrate crystallization from low to high water cut emulsion systems[END_REF] for gas consumption due to hydrate formation in a flowloop of 40 m length and 10.2 mm ID. The fluids considered are methane, deionized water and Kerdane (a light oil with C11 to C14 composition). The case of 40% water cut and 1.36 m/s of mixture superficial velocity was chosen for comparison with the model (water-in-oil emulsion flow). The main characteristics of the experiment are shown in Table 1. The values of the closure parameters used for the model evaluation are presented in Table 2 The number of particles i in the system is estimated by the use of the droplet radius and the total volume of water in the system as:

3 3 4 w total droplet droplet WC i r       ( 11
)
Factor  is introduced to represent the efficiency of particles that are consuming gas. This efficiency is related to the amount of particles that are actually in contact with the bulk, that is, an efficiency due to the impossibility of mass transfer between the particles and the bulk for a dense dispersion and for long distances from the oil-gas interface to the particle. Figure 2 presents the evolution in time of the gas consumption due to hydrate formation. The model is capable of representing the experimental results with the order of magnitude of the closure parameters presented in literature (Table 2) and for a curve fitting of 2.4%   . Initially, hydrates form fast since only crystal integration resistances are present. However, the gas consumption rate decreases with time, with an asymptotic trend related to increased diffusion and permeation resistance as the hydrate shell thickens. Kerdane properties [START_REF]Kerdane D 75 Safety Data Sheet[END_REF] Assumption: diffusivity of methane in Kerdane is one order of magnitude higher than methane in water. Equilibrium fugacity (ideal gas) eq eq fP  Gas fugacity at gas free phase (ideal gas) Droplet size (experimental measurements of [START_REF] Melchuna | Experimental study and modeling of methane hydrates crystallization under flow from emulsions with variable fraction of water and anti-agglomerant[END_REF] for the analyzed case of Table 1) 23

droplet rm  

Conclusions

This study extended the predictive models for hydrate growth in gas-oil-water systems presented by literature. The model was compared with experimental data and the trend of gas consumption over time was validated. The model captures the fast initial growth rate of the hydrates, with an asymptotic trend as the hydrate shell imposes higher mass transfer resistances. The mass transfer resistances are associated with gas diffusion and water permeation trough the hydrate shell, which are related to the shell width and therefore increase in time as the shell becomes thicker.

Figure 1 .

 1 Figure 1. Depiction of mass transfer resistances in the growth kinetics of gas hydrate particles formed as shells contouring water droplets in oil continuous flow.

Figure 2 .

 2 Figure 2. Comparison of model results against experimental data of Melchuna et al. [14] for the amount of gas consumed over time due to hydrate formation. 0 1000 2000 3000 4000 5000 6000 Time [s]

NomenclatureCQ

  Gas concentration [mol/m 3 ] Dh Mass diffusivity of gas inside hydrates [m 2 /s] Hw Henry's constant of gas inside water [mol/(m 3 Pa)] hm Mass transfer coefficient [m/s] i Number of hydrate particles in the system [-] ki Constant of proportionality of the crystal integration rate [mol/(m 2 .s.Pa)] kg/o Absorption coefficient of gas by oil [m/s] g hyd dn dt  Gas consumption rate due to hydrate formation [mol/s] Water permeation flowrate through the hydrate shell [m 3 /s] rin,rout Inner and outer radius of the hydrate particle [m]  Volume [m 3 ] WC Water cut [-]  Hydration number [-] Indexes b Bulk eq Three-phase gas-water-hydrate equilibrium g Gas h Hydrates i Referent to one particle in Inner surface of the particle o Oil out Outer surface of the particle w Water

  .

	, h i hh , 4 h i ii h in out dn dn dn dt dt dt M          	, 22 ,, out i out i in i dr rr dt  , in i dr dt   	(9)
	 bh / 14 g o g o o o h kA dC    / C C g o b 1 dt M	i	,, 22 out i in i dr dr , r , out i r in i dt dt

Table 1 .

 1 . Characteristics of the experiments of Melchuna et al.[START_REF] Melchuna | Topological modeling of methane hydrate crystallization from low to high water cut emulsion systems[END_REF][START_REF] Melchuna | Experimental study and modeling of methane hydrates crystallization under flow from emulsions with variable fraction of water and anti-agglomerant[END_REF].

	Fluids	Methane, deionized water, Kerdane
	Water cut	40%
	Pressure	80 bar
	Temperature	275.5 K
	Mixture superficial velocity	1.36 m/s
	Total liquid volume in the flowloop	10 L

Table 2 .

 2 Closure parameters used for model evaluation.

	Parameter								Value adopted
	Gas diffusivity in hydrate (Davies et al. 2008, apud [15])					h D	13 4 10 m s 2  
	Solubility of gas in solids (order of magnitude from [16])	S	h		1 molgas molsolid  10	(at 80 bar)
	Mass transfer coefficient around a spherical particle (Armenante and Kirwan 1989, apud [11]; estimated for the			m h			 0.15 1.31 10  	3 	s m
	range of rout calculated by the model)
	Constant of proportionality of crystal integration process (order of magnitude from [4])					k	i	6 10 	10 	2 mol m sPa
	Henry's constant of methane in water [17]				H	w	8.9 10 	6 	3 mol
											m Pa
	Henry's constant of methane in Kerdane (calculate from solubility measurements of [14])	H	o	 43 mol m Pa  2.4 10 	
	Absorption coefficient (experimental results of [14] for the analyzed case of Table 1)				/ g o g o kA 	8.1 10 	31 s 
										o
	Properties of methane sI hydrates [15]	h  	917	3 kg m	;	M	h		17.7	g mol
	Assumption: hydrate kinetics cause less cage occupancy										 	6

Acknowledgements

The authors acknowledge the financial support of Région AURA Auvergne Rhône-Alpes through the project COOPERA FluEnergy and TE/CENPES/PETROBRAS.