Special Issue – Developments in Language Theory (DLT 2010)No Access

EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS

SYLVIA FRIESE

Technische Universität München, Garching, Germany

Search for more papers by this author

HELMUT SEIDL

Technische Universität München, Garching, Germany

Search for more papers by this author

, and

SEBASTIAN MANETH

NICTA and University of New South Wales, Sydney, Australia

Search for more papers by this author

https://doi.org/10.1142/S012905411100891XCited by:3 (Source: Crossref)

Abstract

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

Keywords:

References

A. V. Aho and J. D. Ullman, Inform. and Control 19, 439 (1971). Crossref, Google Scholar
J. Berstel , Transductions and Context-Free Languages ( Teubner , Stuttgart , 1979 ) . Crossref, Google Scholar
B. Courcelle and P. Franchi-Zannettacci, Inform. and Control 52, 275 (1982). Crossref, Google Scholar
J. Engelfriet, Math. Systems Theory 9, 198 (1975), DOI: 10.1007/BF01704020. Crossref, Google Scholar
J. Engelfriet, Math. Systems Theory 10, 289 (1977), DOI: 10.1007/BF01683280. Crossref, Google Scholar
J. Engelfriet, Formal language theory; perspectives and open problems, ed. R. V. Book (Academic Press, New York, 1980) pp. 241–286. Crossref, Google Scholar
J. Engelfriet and S. Maneth, Inform. and Comput. 154, 34 (1999), DOI: 10.1006/inco.1999.2807. Crossref, Web of Science, Google Scholar
J. Engelfriet and S. Maneth, SIAM J. Comput. 32, 950 (2003), DOI: 10.1137/S0097539701394511. Crossref, Web of Science, Google Scholar
J. Engelfriet and S. Maneth, Inform. Proc. Letters 100, 206 (2006). Crossref, Web of Science, Google Scholar
J. Engelfriet, S. Maneth and H. Seidl, J. Comput. Syst. Sci. 75(5), 271 (2009), DOI: 10.1016/j.jcss.2009.01.001. Crossref, Web of Science, Google Scholar
Z. Ésik, Acta Cybernetica 5, 1 (1980). Google Scholar
E. Filiotet al., Properties of visibly pushdown transducers, MFCS 2010 (Brno Czech Republic, 2010) pp. 355–367. Google Scholar
S. Friese, H. Seidl and S. Maneth, Minimization of deterministic bottom-up tree transducers, DLT (Springer-Verlag, Berlin, Heidelberg, 2010) pp. 185–196. Google Scholar
Z. Fülöp, Acta Cybernetica 5, 261 (1981). Google Scholar
Z. Fülöp and S. Vágvölgyi, Inform. and Comput. 116, 231 (1995). Crossref, Web of Science, Google Scholar
Z. Fülöp and H. Vogler , Syntax-Directed Semantics – Formal Models based on Tree Transducers , EATCS Monographs in Theoretical Computer Science , eds. W. Brauer , G. Rozenberg and A. Salomaa ( Springer-Verlag , 1998 ) . Crossref, Google Scholar
Z. Gazdag, Int. J. Found. Comput. Sci. 17(2), 395 (2006). Link, Web of Science, Google Scholar
D. E. Knuth, Math. Systems Theory 2, 127 (1968), DOI: 10.1007/BF01692511. Crossref, Google Scholar
G. Laurence et al. , Normalization of Sequential Top-Down Tree-to-Word Transducers , LATA , LNCS ( Springer , Tarragona, Spain , 2011 ) . Google Scholar
A. Lemay, S. Maneth and J. Niehren, A learning algorithm for top-down xml transformations, PODS 2010, Proceedings (ACM, New York, NY, USA, 2010) pp. 285–296. Google Scholar
M. Mohri, Theor. Comput. Sci. 234, 177 (2000), DOI: 10.1016/S0304-3975(98)00115-7. Crossref, Web of Science, Google Scholar
W. C. Rounds, Math. Systems Theory 4, 257 (1970), DOI: 10.1007/BF01695769. Crossref, Google Scholar
H. Seidl, Theor. Comput. Sci. 106(1), 135 (1992), DOI: 10.1016/0304-3975(92)90281-J. Crossref, Web of Science, Google Scholar
J. W. Thatcher, J. Comp. Syst. Sci. 4, 339 (1970), DOI: 10.1016/S0022-0000(70)80017-4. Crossref, Web of Science, Google Scholar
J. W. Thatcher, Currents in the Theory of Computing, ed. A. V. Aho (Prentice Hall, 1973) pp. 143–172. Google Scholar
Z. Zachar, Acta Cybernetica 4, 167 (1980). Google Scholar