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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.