Rational stochastic automata in formal language theory
Paavo Turakainen (1982)
Banach Center Publications
Similarity:
Paavo Turakainen (1982)
Banach Center Publications
Similarity:
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...
Olivier Finkel (2009)
RAIRO - Theoretical Informatics and Applications
Similarity:
We show that many classical decision problems about -counter -languages, context free -languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free -languages or for infinitary...
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...
Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.
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...