Decomposing a k-valued transducer into k unambiguous ones
Weber, Andreas
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 379-413 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@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},
     volume = {30},
     year = {1996},
     pages = {379-413},
     mrnumber = {1435729},
     zbl = {0867.68046},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 379-413. http://gdmltest.u-ga.fr/item/ITA_1996__30_5_379_0/

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

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

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

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

[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 689490 | Zbl 0502.68022

[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 921501 | Zbl 0637.68093

[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 1288776 | Zbl 0925.68324

[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 577064 | Zbl 0368.20023

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

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

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

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

[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 1253375

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

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

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