Closure under union and composition of iterated rational transductions
D. Simplot, A. Terlutte (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
D. Simplot, A. Terlutte (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Alain Terlutte, David Simplot (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Tomasz Jurdziński, Friedrich Otto (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
As already 2-monotone -automata accept -complete languages, we introduce a restricted variant of -monotonicity for restarting automata, called . For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that -automata that are sequentially monotone of degree for any only accept context-free languages. ...
D. Simplot, A. Terlutte (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.
Sylvain Lombardy, Jacques Sakarovitch (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms...
Sylvain Lombardy, Jean Mairesse (2006)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Consider partial maps with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one...
Marie-Pierre Béal, Olivier Carton (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Sylvain Lombardy, Jacques Sakarovitch (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
In this paper we investigate how it is possible to recover an automaton from a rational expression that has been computed from that automaton. The notion of derived term of an expression, introduced by Antimirov, appears to be instrumental in this problem. The second important ingredient is the co-minimization of an automaton, a dual and generalized Moore algorithm on non-deterministic automata. We show here that if an automaton is then sufficiently “decorated”, the combination of these...