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 two algorithms...
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 that recognize...
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...
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 that recognize the same series.
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
of an...
Download Results (CSV)