Decomposing a k -valued transducer into k unambiguous ones

Andreas Weber

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 5, page 379-413
  • ISSN: 0988-3754

How to cite

top

Weber, Andreas. "Decomposing a $k$-valued transducer into $k$ unambiguous ones." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.5 (1996): 379-413. <http://eudml.org/doc/92542>.

@article{Weber1996,
author = {Weber, Andreas},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {transducer models; nondeterministic generalized sequential machine},
language = {eng},
number = {5},
pages = {379-413},
publisher = {EDP-Sciences},
title = {Decomposing a $k$-valued transducer into $k$ unambiguous ones},
url = {http://eudml.org/doc/92542},
volume = {30},
year = {1996},
}

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
PB - EDP-Sciences
VL - 30
IS - 5
SP - 379
EP - 413
LA - eng
KW - transducer models; nondeterministic generalized sequential machine
UR - http://eudml.org/doc/92542
ER -

References

top
  1. [B79] J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart, Germany, 1979. Zbl0424.68040MR549481
  2. [CLR90] T. CORMEN, C. LEISERSON and R. RIVEST, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. Zbl1158.68538MR1066870
  3. [C90] K. CULIK II, New techniques for proving the decidability of equivalence problems. Theorical Computer Science, 1990, 71, pp. 29-45. Zbl0699.68092MR1050077
  4. [E74] S. EILENBERG, Automata, Languages, and Machines, Volume A, Academic Press, New York, NY, 1974. Zbl0317.94045MR530382
  5. [G89] E. GURARI, An Introduction to the Theory of Computation, Computer Science Press, Rockville, MD, 1989. 
  6. [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
  7. [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
  8. [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
  9. [Li91] L. P. LISOVIK, personal communication, 1991. 
  10. [LS77] R. LYNDON and P. SCHUPP, Combinatorial Group Theory, Springer-Verlag, Berlin, Heidelberg, Germany, New York, NY, 1977. Zbl0368.20023MR577064
  11. [Sch76] M. P. SCHÜTZENBERGER, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Science, 1976, 3, pp. 243-259. Zbl0358.68129MR445927
  12. [Se94] H. SEIDL, Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, 1994, 27, pp. 285-346. Zbl0809.68087MR1272634
  13. [W90] A. WEBER, On the valuedness of finite transducers, Acta Informatica, 1990, 27, pp. 749-780. Zbl0672.68027MR1080581
  14. [W92a] A. WEBER, On the lengths of values in a finite transducer, Acta Informatica, 1992, 29, pp. 663-687. Zbl0790.68038MR1190552
  15. [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
  16. [W93] A. WEBER, Decomposing finite-valued transducers and deciding their equivalence, SIAM J. Computing, 1993, 22, pp. 175-202. Zbl0767.68079MR1202868
  17. [W94] A. WEBER, Finite-valued distance automata, Theoretical Computer Science, 1994, 134, pp. 225-251. Zbl0938.68709MR1299375
  18. [WK95] A. WEBER and R. KLEMM, Economy of description for single-valued transducers, Information and Computation, 1995, 118, pp. 327-340. Zbl0826.68065MR1331733

NotesEmbed ?

top

You must be logged in to post comments.