Arrow Research search

Author name cluster

Michel Latteux

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

TCS Journal 2019 Journal Article

On prefixal one-rule string rewrite systems

  • Michel Latteux
  • Yves Roos

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.

Details DOI

I&C Journal 2015 Journal Article

A canonical automaton for one-rule length-preserving string rewrite systems

  • Michel Latteux
  • Yves Roos

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 × 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.

Details DOI

TCS Journal 2007 Journal Article

Extension of the decidability of the marked PCP to instances with unique blocks

  • Vesa Halava
  • Tero Harju
  • Juhani Karhumäki
  • Michel Latteux

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.

Details DOI

TCS Journal 2006 Journal Article

Identification of biRFSA languages

  • Michel Latteux
  • Aurélien Lemay
  • Yves Roos
  • Alain Terlutte

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 identified in this framework is an interesting problem. One of the most classical identifiable 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 identifiable in general but we present two subclasses that are learnable, the second one being identifiable in polynomial time.

Details DOI

TCS Journal 2005 Journal Article

Commutation with codes

  • Juhani Karhumäki
  • Michel Latteux
  • Ion Petre

The centralizer of a set of words X is the largest set of words C ( X ) commuting with X: X C ( X ) = C ( X ) X. It has been a long standing open question due to [J. H. Conway, Regular Algebra and Finite Machines, Chapman & Hall, London (1971). ], whether the centralizer of any rational set is rational. While the answer turned out to be negative in general, see [M. Kunc, Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, Springer, Berlin, 2004, pp. 870–881. ], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. This result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [B. Ratoandromanana, RAIRO Inform. Theor. 23(4) (1989) 425–444. ]—many of the techniques we use in this paper follow her ideas. We also give in this paper an elementary proof for the prefix case.

Details DOI

TCS Journal 2005 Journal Article

Mixed languages

  • Jean Berstel
  • Luc Boasson
  • Michel Latteux

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.

Details DOI

MFCS Conference 1998 Conference Paper

Iterated Length-Preserving Rational Transductions

  • Michel Latteux
  • David Simplot
  • Alain Terlutte

Abstract 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”.

Details

TCS Journal 1998 Journal Article

The meet operation in the lattice of codes

  • Véronique Bruyère
  • Denis Derencourt
  • Michel Latteux

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.

Details DOI

TCS Journal 1997 Journal Article

Recognizable picture languages and domino tiling

  • Michel Latteux
  • David Simplot

In [2], Giammarresi and Restivo define the notion of local picture languages by giving a set of authorized 2 × 2 tiles over ∑ ∪ {#} where # is a boundary symbol which surrounds the pictures. Then they define the class of recognizable picture languages as the set of languages which can be obtained by projection of a local one. This class is of interest since it admits several quite different characterizations [3]. Here, we define the hv-local picture languages where 2 × 2 tiles are replaced by horizontal and vertical dominoes. So the horizontal and the vertical scanning can be done separately. However, we prove that every recognizable picture language can be obtained as a projection of a hv-local language.

Details DOI

MFCS Conference 1992 Conference Paper

On Computational Power of Weighted Finite Automata

  • Denis Derencourt
  • Juhani Karhumäki
  • Michel Latteux
  • Alain Terlutte

Abstract 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.

Details

MFCS Conference 1990 Conference Paper

Rational omega-Transductions

  • Michel Latteux
  • Erick Timmerman

Abstract 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.

Details

TCS Journal 1988 Journal Article

2-Asynchronous automata

  • Robert Cori
  • Eric Sopena
  • Michel Latteux
  • Yves Roos

W. Zielonka has recently introduced a family of finite automata with a specific behavior, and called them asynchronous automata. They can be considered as a good model to describe concurrent processes exchanging data by means of some common storage. Hereafter, we restrict the family of asynchronous automata by defining the subclass of what we will call 2-asynchronous automata. We illustrate this subclass by a communication problem involving mailboxes, and prove that 2-asynchronous automata are as powerful as asynchronous ones.

Details DOI

FOCS Conference 1982 Conference Paper

Substitution of Bounded Rational Cone

  • Joffroy Beauquier
  • Michel Latteux

We study the family S of rational cones obtained by iterated substitutions from rational cones L1, .. , Ln. This family is a semi-group and to every non empty word u defined on the alphabet {L1, .. ., Ln}, corresponds a rational cone U of S. We give sufficient conditions for S to be free (U = U′ implies u = u′) and to verify the subpattern property (U ⊂ U′ implies u is a subpattern of u′). We study, more particularly, the case where L1, .. ., Ln are bounded rational cones.

Details

TCS Journal 1981 Journal Article

A propos du lemme de substitution

  • Michel Latteux

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.

Details DOI

TCS Journal 1977 Journal Article

Produit dans le cône rationnel engendré par D*1

  • Michel Latteux

Nous montrons que si le cône rationnel généré par D * 1, le langage de Dyck sur une lettre, contient le produit de deux langages définis sur des alphabets disjoints, nécessairement l'un des deux langages est rationnel. Cette propriété n'est pas vraie pour le cône rationnel généré par D' * 1, le langage de semi-Dyck sur une lettre.

Details DOI
v2026.09.13