Decomposing a k-valued transducer into k unambiguous ones
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 5, pp. 379-413.
@article{ITA_1996__30_5_379_0,
     author = {Weber, Andreas},
     title = {Decomposing a $k$-valued transducer into $k$ unambiguous ones},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {379--413},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {5},
     year = {1996},
     mrnumber = {1435729},
     zbl = {0867.68046},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1996__30_5_379_0/}
}
TY  - JOUR
AU  - Weber, Andreas
TI  - Decomposing a $k$-valued transducer into $k$ unambiguous ones
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 379
EP  - 413
VL  - 30
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_5_379_0/
LA  - en
ID  - ITA_1996__30_5_379_0
ER  - 
%0 Journal Article
%A Weber, Andreas
%T Decomposing a $k$-valued transducer into $k$ unambiguous ones
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 379-413
%V 30
%N 5
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1996__30_5_379_0/
%G en
%F ITA_1996__30_5_379_0
Weber, Andreas. Decomposing a $k$-valued transducer into $k$ unambiguous ones. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 5, pp. 379-413. http://www.numdam.org/item/ITA_1996__30_5_379_0/

[B79] J. Berstel, Transductions and Context-Free Languages, Teubner, Stuttgart, Germany, 1979. | MR | Zbl

[CLR90] T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. | MR | Zbl

[C90] K. Culik Ii, New techniques for proving the decidability of equivalence problems. Theorical Computer Science, 1990, 71, pp. 29-45. | MR | Zbl

[E74] S. Eilenberg, Automata, Languages, and Machines, Volume A, Academic Press, New York, NY, 1974. | MR | Zbl

[G89] E. Gurari, An Introduction to the Theory of Computation, Computer Science Press, Rockville, MD, 1989.

[GI83] E. Gurari and O. Ibarra, A note on finite-valued and finitely ambiguous transducers, Mathematical Systems Theory, 1983, 16, pp. 61-66. | MR | Zbl

[K87] J. Karhumäki, The equivalence of mappings on languages, Proc. 4th IMYCS 1986, in: Lecture Notes in Computer Science, No. 281, Springer-Verlag, Berlin, Heidelberg, Germany, 1987, pp. 26-38. | MR | Zbl

[Le93] H. Leung, Separating exponentially ambiguous NFA from polynomially ambiguous NFA, Proc. 4th ISAAC 1993, in: Lecture Notes in Computer Science, No. 762, Springer-Verlag, Berlin, Heidelberg, Germany, 1993, pp. 221-229. | MR | Zbl

[Li91] L. P. Lisovik, personal communication, 1991.

[LS77] R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer-Verlag, Berlin, Heidelberg, Germany, New York, NY, 1977. | MR | Zbl

[Sch76] M. P. Schützenberger, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Science, 1976, 3, pp. 243-259. | MR | Zbl

[Se94] H. Seidl, Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, 1994, 27, pp. 285-346. | MR | Zbl

[W90] A. Weber, On the valuedness of finite transducers, Acta Informatica, 1990, 27, pp. 749-780. | MR | Zbl

[W92a] A. Weber, On the lengths of values in a finite transducer, Acta Informatica, 1992, 29, pp. 663-687. | MR | Zbl

[W92b] A. Weber, Decomposing a k-valued transducer into k unambiguous ones, Proc. 1st LATIN 1992, in: Lecture Notes in Computer Science, No. 583, Springer-Verlag, Berlin, Heidelberg, Germany, 1992, pp. 503-515. | MR

[W93] A. Weber, Decomposing finite-valued transducers and deciding their equivalence, SIAM J. Computing, 1993, 22, pp. 175-202. | MR | Zbl

[W94] A. Weber, Finite-valued distance automata, Theoretical Computer Science, 1994, 134, pp. 225-251. | MR | Zbl

[WK95] A. Weber and R. Klemm, Economy of description for single-valued transducers, Information and Computation, 1995, 118, pp. 327-340. | MR | Zbl