EUDML

Currently displaying 1 – 12 of 12

Order by Relevance | Title | Year of publication

Cônes rationnels commutativement clos

Michel Latteux — 1977

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Sur les TOL - Systèmes unaires

Michel Latteux — 1975

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Mots infinis et langages commutatifs

Michel Latteux — 1978

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Sur les ensembles linéaires

Michel Latteux — 1987

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux; Yves Roos — 2014

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 and the right-hand side of the rule of the system are not quasi-conjugate or are equal, that means if and are distinct, there do not exist words , and such that = and = . We prove the part...

Minimal NFA and biRFSA languages

Michel Latteux; Yves Roos; Alain Terlutte — 2009

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Minimal NFA and biRFSA Languages

Michel Latteux; Yves Roos; Alain Terlutte — 2008

RAIRO - Theoretical Informatics and Applications

Indécidabilité de la condition IRS

Jean-Michel Autebert; Joffroy Beauquier; Luc Boasson; Michel Latteux — 1982

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Motifs et bases de langages

Jean-Michel Autebert; Luc Boasson; Michel Latteux — 1989

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Equality sets for recursively enumerable languages

Vesa Halava; Tero Harju; Hendrik Jan Hoogeboom; Michel Latteux — 2005

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider shifted equality sets of the form $E_{G} (a, g_{1}, g_{2}) = {w ∣ g_{1} (w) = a g_{2} (w)}$ , where $g_{1}$ and $g_{2}$ are nonerasing morphisms and $a$ is a letter. We are interested in the family consisting of the languages $h (E_{G} (J))$ , where $h$ is a coding and $E_{G} (J)$ is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language $L \subseteq A^{*}$ is a projection of a shifted equality set, that is, $L = π_{A} (E_{G} (a, g_{1}, g_{2}))$ for some (nonerasing) morphisms $g_{1}$ and $g_{2}$ and a letter $a$ , where $π_{A}$ deletes the letters not in $A$ . Then we deduce...

Equality sets for recursively enumerable languages

Vesa Halava; Tero Harju; Hendrik Jan Hoogeboom; Michel Latteux — 2010

RAIRO - Theoretical Informatics and Applications

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter...