On the decomposition of k-valued rational relations

Details On the decomposition of k-valued rational relations On the decomposition of k-valued rational relations

2008-02-20

arxiv.org/abs/0802.2823v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Information Theory

Scientific paper

We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential. Moreover, this method allows further generalisation that solves the problem of decomposition of rational relations with bounded length-degree, which was left open in Weber's paper.

Affiliated with

Also associated with

No associations

Rating

On the decomposition of k-valued rational relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the decomposition of k-valued rational relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the decomposition of k-valued rational relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647728