A Combinatorial Study of k-Valued Rational Relations

We give combinatorial proofs for three fundamental properties of k-valued rational relations: the decomposition of a k-valued rational relation into a union of k rational functions; the decidability of the k-valuedness; the decidability of the equivalence for k-valued rational relations. Positive answers are already known for these properties. Our contribution lies in the fact that our proofs are built on few elementary combinatorial arguments, which make them considerably shorter and hopefully easier to understand. In particular, in order to tackle the k-valuedness, we generalize a combinatorial characterization of the rational functions due to Schutzenberger.