Decomposing a -valued transducer into unambiguous ones
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)
- Volume: 30, Issue: 5, page 379-413
- ISSN: 0988-3754
Access Full Article
topHow to cite
topReferences
top- [B79] J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart, Germany, 1979. Zbl0424.68040MR549481
- [CLR90] T. CORMEN, C. LEISERSON and R. RIVEST, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. Zbl1158.68538MR1066870
- [C90] K. CULIK II, New techniques for proving the decidability of equivalence problems. Theorical Computer Science, 1990, 71, pp. 29-45. Zbl0699.68092MR1050077
- [E74] S. EILENBERG, Automata, Languages, and Machines, Volume A, Academic Press, New York, NY, 1974. Zbl0317.94045MR530382
- [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. Zbl0502.68022MR689490
- [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. Zbl0637.68093MR921501
- [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. Zbl0925.68324MR1288776
- [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. Zbl0368.20023MR577064
- [Sch76] M. P. SCHÜTZENBERGER, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Science, 1976, 3, pp. 243-259. Zbl0358.68129MR445927
- [Se94] H. SEIDL, Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, 1994, 27, pp. 285-346. Zbl0809.68087MR1272634
- [W90] A. WEBER, On the valuedness of finite transducers, Acta Informatica, 1990, 27, pp. 749-780. Zbl0672.68027MR1080581
- [W92a] A. WEBER, On the lengths of values in a finite transducer, Acta Informatica, 1992, 29, pp. 663-687. Zbl0790.68038MR1190552
- [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. MR1253375
- [W93] A. WEBER, Decomposing finite-valued transducers and deciding their equivalence, SIAM J. Computing, 1993, 22, pp. 175-202. Zbl0767.68079MR1202868
- [W94] A. WEBER, Finite-valued distance automata, Theoretical Computer Science, 1994, 134, pp. 225-251. Zbl0938.68709MR1299375
- [WK95] A. WEBER and R. KLEMM, Economy of description for single-valued transducers, Information and Computation, 1995, 118, pp. 327-340. Zbl0826.68065MR1331733