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...
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...
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...
Download Results (CSV)