Search

International audience; Prefixal one-rule string rewrite systems are one-rule string rewrite systems for which the left-hand side of the rule is a prefix of the right-hand side of the rule. String rewrite systems induce a transformation over languages: from a starting word, one can associate all its descendants. We prove, in this work, that the transformation induced by a prefixal one-rule rewrite system always transforms a finite language into a context-free language, a property that is surprisingly not satisfied by arbitrary one-rule rewrite systems. We also give here a decidable characterization of the prefixal one-rule rewrite systems whose induced transformation is a rational transduction.

In the Post Correspondence Problem (PCP) an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w)=g(w). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances.

International audience; In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A x A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.

We consider shifted equality sets of the form EG(a, g1 ,g 2 )= {w | g1(w )= ag2(w)} ,w hereg1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and EG(J )i s as hifted equality set. We prove several closure properties for this family. More- over, we show that every recursively enumerable language L ⊆ A ∗ is a projection of a shifted equality set, that is, L = πA(EG(a, g1 ,g 2)) for some (nonerasing) morphisms g1 and g2 and a letter a ,w hereπA deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets. Mathematics Subject Classification. 03D25, 68Q45.

We consider equality sets of prefix morphisms, that is, sets E(g"1,g"2)={w|g"1(w)=g"2(w)}, where g"1 and g"2 are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form @p"A(E(g"1,g"2)) for some prefix morphisms g"1 and g"2, and a projection @p"A which deletes the letters not in A.

Let T=A∪B∪C be an alphabet that is partitioned into three subalphabets. The mixing product of a word g over A∪B and of a word d over A∪C is the set of words w over T such that its projection onto A∪B gives g and its projection onto A∪C gives d.Let R be a regular language over T such that xbcy is in R if and only if xcby is in R for any two letters b in B and c in C. In other words, R is commutative over B and C. Is this property “structural” in the sense that R can then be obtained as a mixing product of a regular language over A∪B and of a regular language over A∪C?This question has a rather easy answer, but there are many cases where the answer is negative. A more interesting question is whether R can be represented as a finite union of mixed products of regular languages. For the moment, we do not have an answer to this question. However, we prove that it is decidable whether, for a given k, the language R is a union of at most k mixed products of regular languages.RésuméSoit T=A∪B∪C un alphabet partitionné en trois sous-alphabets. Le mélange d’un mot g sur A∪B et d’un mot d sur A∪C est l’ensemble des mots w sur T dont la projection sur A∪B donne le mot g et sur A∪C donne le mot d.Soit R un langage rationnel sur T tel que xbcy est dans R si et seulement si xcby est dans R pour deux lettres quelconques b∈B et c∈C. En d’autres termes, R est commutatif sur B et C. Est-ce que cette propriété est “structurelle”, c’est-à-dire peut-on alors obtenir R comme mélange d’un langage rationnel sur A∪B et d’un langage rationnel sur A∪C?Cette question a une réponse plutôt facile, mais il existe de trop nombreux cas où la réponse est négative. Une question plus intéressante est de savoir si on peut représenter R comme une union finie de mélanges de langages rationnels. Pour l’instant, nous n’avons pas de réponse à cette question. En revanche, nous montrons qu’il est décidable, pour un entier k donné, si R est union d’au plus k mélanges de langages rationnels.

We prove that for any nonperiodic set of words F \subseteq Σ+ with at most three elements, the centralizer of F, i.e., the largest set commuting with F, is F*. Moreover, any set X commuting with F is of the form X = FI, for some I \subseteq ℕ. A boundary point is thus established, as these results do not hold for all languages with at least four words. This solves a conjecture of Karhumaki and Petre, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana and Conway.

International audience; We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u=xyz and v=zyx. We prove the only if part of this conjecture and identify two non trivial cases where the if part is satisfied.; Nous étudions le problème de la caractérisation des systèmes de réécriture à une règle préservant les longueurs pour lesquels la relation re réécriture associée est rationnelle. Nous répondons partiellement à une conjecture d'Éric Lilin de 1991 stipulant qu'un système de réécriture à une règle préservant les longueurs est une transduction rationnelle si et seulement si la partie gauche u et la partie droite v de l'unique règle de réécriture du système ne sont pas quasi-conjugués ou u et v sont égaux, c'est à dire que si u et v sont différents, il n'existe pas trois mots x, y et z tels que u = xyz et v = zyx. Nous montrons que la condition est nécessaire et nous identifions deux cas significatifs pour lesquels la condition est suffisante.

We study properties of the meet of two rational codes X and Y, defined as the base of the free monoid X∗∩Y∗. We first give several examples of rational maximal codes Xand Y such that their meet is no longer a maximal code. We give a combinatorial characterization of the rational maximal codes X,Y for which the meet is a maximal code. We also show that any rational (maximal or not) code is the meet of two rational maximal codes.

Weighted Finite Automata are automata with multiplicities used to compute real functions by reading infinite words. The aim of this paper is to study what kind of functions can be computed by level automata, a particular subclass of WFA. Several results concerning the continuity and the smoothness of these functions are shown. In particular, the only smooth functions that can be obtained are the polynomials. This enables to decide whether a function computed by a level automaton is smooth or not.

International audience; The family of one-rule grid semi-Thue systems, introduced by Alfons Geser, is the family of one-rule semi-Thue systems such that there exists a letter c that occurs as often in the left-hand side as the right-hand side of the rewriting rule. We prove that for any one-rule grid semi-Thue system S, the set S(w) of all words obtainable from w using repeatedly the rewriting rule of S is a constructible context-free language. We also prove the regularity of the set Loop(S) of all words that start a loop in a one-rule grid semi-Thue systems S.; La famille des systèmes de semi-Thue à une seule règle "en grille", introduite par Alfons Geser, est la famille des systèmes de réécriture de mots pour lesquels il existe une lettre apparaissant autant de fois dans la partie gauche et dans la partie droite de leur unique règle. Nous prouvons que, pour tout système S de cette famille, l'ensemble S(w) des mots obtenus à partir du mot w en appliquant itérativement la règle de réécriture de S est un langage algébrique constructible. Nous prouvons également que l'ensemble Loop(S) des mots qui sont à l'origine d'une boucle de réécriture pour un systèmes de semi-Thue à une seule règle "en grille" S est un langage régulier.

Weighted Finite Automata (WFA) can be used to define functions from [0, 1] into R. We give here a method to construct more and more complex WFA computing continuous functions. We give also an example of a continuous function having no derivative at any point, that can be computed with a 4-state WFA

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions ℋ ℋP−1 ℋ, where ℋP consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions ℋ ℳℋP−1 ℛ ℋ , where ℳ is the family of endmarkers and ℛ is the family of removals of endmarkers. (The compositions are read from left to right). We also show that ℳ ℋℋP−1 ℋ is the family of the subsequential functions.

On montre que les fonctions rationnelles coincident avec les compositions de marquages terminaux, morphismes et inverses de morphismes, injectifs. Plus precisement, toute fonction rationnelle τ se represente sous la forme τ=μ m α 1 α 2 −1 α 3 ou μ m est un marquage terminal, α 1 , α 3 sont des morphismes et α 2 est un morphisme injectif

International audience; In this paper, we define the notion of biRFSA which is a residual finate state automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by such automata are called biRFSA languages. We prove that the canonical RFSA of a biRFSA language is a minimal NFA for this language and that each minimal NFA for this language is a sub-automaton of the canonical RFSA. This leads to a characterization of the family of biRFSA languages. In the second part of this paper, we define the family of biseparable automata. We prove that every biseparable NFA is uniquely minimal among all NFAs recognizing a same language, improving the result of H. Tamm and E. Ukkonen for bideterministic automata.

Geffert has shown that earch recursively enumerable languageL overΣ can be expressed in the formL{h(x) ?1 g(x)?x inΔ +}?Σ * whereΔ is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =?(L 0)?Σ * whereL 0 is a minimal linear language and ? is the Dyck reductionaa???, Aa???.

International audience; The task of identifying a language from a set of its words is not an easy one. For instance, it is not feasible to identify regular languages in the general case. Therefore, looking for subclasses of regular languages that can be identi?ed in this framework is an interesting problem. One of the most classical identi?able classes is the class of reversible languages, introduced by D. Angluin, also called bideterministic languages as they can be represented by deterministic automata (DFA) whose reverse is also deterministic. Residual Finite State Automata (RFSA) on the other hand is a class of non deterministic automata that shares some properties with DFA. In particular, DFA are RFSA and RFSA can be much smaller. We study here learnability of the class of languages that can be represented by biRFSA: RFSA whose reverse are RFSA. We prove that this class is not identi?able in general but we present two subclasses that are learnable, the second one being identi?able in polynomial time.

In order to study composition of morphisms and inverse morphisms, we introduce starry transductions t which are, by definition, those verifying: e ∃ t(e) and for all words u, v, t(u) t(v) ⊂t(uv). We show that each starry transduction can be factored with two morphisms and two inverse morphisms. Then, we study some particular starry transductions. So, we prove that each rational substitution can be factored into a single morphism and two inverse morphisms and that each decreasing starry transduction can be factored into a single inverse morphism and two morphisms. That permits us to give an answer to a question posed in [5], by showing that for every rational language R, there exist morphisms h1, h2, h3, g1, g2, g3, such that R=h 3 −1 o h2 o h 1 −1 (a)=g3 o g 2 −1 o g1(a*b).

The rational ω-transductions (defined by F. Gire as bimorphisms) are particular transductions for infinite words. In this paper we give characterizations of these transductions. On the one hand they coincide with the compositions of non erasing and inverse non erasing morphisms, and only three morphisms are necessary. On the other hand they can be defined from bifaithful rational transductions using a limit operation we call adherence.

This survey presents some results concerning total commutations, partial commutations and semi-commutations in connection with the families of rational and algebraic languages and more generaly with (faithful) rational cones.

We study restricted one counter languages, that is, languages belonging to Rocl, the full trio generated by D1′*, the restricted Dyck language over one pair of parentheses. We show that every generator of Rocl is a bifaithfull one and that there exists a one counter language which dominates the other ones by length preserving rational transduction. Then, we establish that the pumping lemma for linear languages is almost true for restricted one counter languages. At last, we prove that Rocl contains no non-rational AFL and, if Rocl is included in the smallest full AFL containing a full semi-AFL L, then Rocl is included in L. Moreover, if Rocl is included in the smallest full AFL closed under substitution containing a context-free full trio L, then Rocl is included in L.

New representation results for three families of regular languages are stated, using a special kind of shuffle operation, namely the synchronized shuffle. First, it is proved that the family of regular star languages is the smallest family containing the language (a + bc)* and closed under synchronized shuffle and length preserving morphism. The second representation result states that the family of e-free regular languages is the smallest family containing the language (a + bc)*d and closed under synchronized shuffle, union and length preserving morphism. At last, it is proved that Reg is the smallest family containing the two languages (a+ bb)* and a+(ab)+, closed under synchronized shuffle, union and length preserving morphism.

The purpose of this paper is the study of the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving transductions, by showing the connections with “context-sensitive transductions” and transductions associated with recognizable picture languages. We also study the class obtained by only using length-preserving rational functions and we show the relations with “deterministic context-sensitive transductions”.

We state a simple condition on a rational subset X of a free monoid B* for the existence of a sequential function that is a one-to-one mapping of some free monoid A* onto X. As a by-product we obtain new sequential bijections of a free monoid onto another.

Weighted Finite Automata are automata with multiplicities used to compute real functions by reading infinite words. We study what kind of functions can be computed by level automata, a particular subclass of WFA. Several results concerning the continuity and the smoothness of these functions are shown. In particular, the only smooth functions that can be obtained are the polynomials. This allows to decide whether a function computed by a level automaton is smooth or not.

A polyomino contour can be represented as a word over a four letter alphabet A. Each letter induces a unit line pointing one of the four directions (right, left, up and down). According to[b], checking whether a rational language R⊂A* contains a polyomino contour word is undecidable. We restrict the problem to convex polyominoes and we prove that, in this case, the problem turns out to be decidable.

We establish a new version of the Greibach syntactic lemma regarding substitutions between full trios, namely: Let ℒ 1 be a bifaithful trio, ℒ 2 a full trio, L 1 , L 2 languages over disjoint alphabets. Then L 1 ↑ℒ 2 ∈ℒ 1 □ℒ 2 implies L 1 ∈ℒ 1 or ( L 2 c ) * ∈ℒ 2 .

We study the family SLB of morphic images of the intersection of two bounded Context-free languages. In particular, we prove the equality between this family and the family of finite intersection of bounded Context-free languages.

Tout ensemble ayant G comme ensemble de periodes est une union finie disjointe d'ensembles lineaires dont les periodes appartiennent a G