The Myhill-Nerode Theorem for Recognizable Tree Series

  • Björn Borchardt
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


In this paper we prove a Myhill-Nerode theorem for recognizable tree series over commutative semifields and thereby present a minimization of bottom-up finite state weighted tree automata over a commutative semifield, where minimal means with respect to the number of states among all equivalent, deterministic devices.


Formal Power Series Tree Representation Congruence Relation Tree Series Tree Automaton 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    J. Berstel and C. Reutenauer. Recognizable formal power series on trees. Theoretical Computer Science, 18:115–148, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  2. [2]
    J. Berstel and Ch. Reutenauer. Rational Series and Their Languages, volume 12 of EATCS-Monographs. Springer Verlag, 1988.Google Scholar
  3. [3]
    B. Borchardt and H. Vogler. Determinization of Finite State Weighted Tree Automata. J. Automata, Languages and Combinatorics, accepted, 2003.Google Scholar
  4. [4]
    S. Bozapalidis. Effective constuction of the syntactic algebra of a recognizable series on trees. Acta Informatica, 28:351–363, 1991.zbMATHCrossRefMathSciNetGoogle Scholar
  5. [5]
    J. Doner. Tree acceptors and some of their applications. J. Comput. System Sci., 4:406–451, 1970.zbMATHCrossRefMathSciNetGoogle Scholar
  6. [6]
    M. Droste and P. Gastin. The Kleene-Schützenberger theorem for formal power series in partially commuting variables. Information and Computation, 153:47–80, 1999. extended abstract in: 24th ICALP, LNCS vol. 1256, Springer, 1997, pp. 682–692.zbMATHCrossRefMathSciNetGoogle Scholar
  7. [7]
    M. Droste and D. Kuske. Skew and infinitary formal power series. Technical Report 2002-38, Department of Mathematics and Computer Science, University of Leicester, 2002.Google Scholar
  8. [8]
    S. Eilenberg. Automata, Languages, and Machines, Vol.A. Academic Press, 1974.Google Scholar
  9. [9]
    Z. Esik and W. Kuich. Formal Tree Series. J. Automata, Languages and Combinatorics, accepted, 2003.Google Scholar
  10. [10]
    Z. Fülöp and S. Vágvölgyi. Congruential tree languages are the same as recognizable tree languages. Bulletin of EATCS, 30:175–185, 1989.Google Scholar
  11. [11]
    Z. Fülöp and H. Vogler. Tree series transformations that respect copying. Theory of Computing Systems, to appear, 2003.Google Scholar
  12. [12]
    F. Gécseg and M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.zbMATHGoogle Scholar
  13. [13]
    F. Gécseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer-Verlag, 1997.Google Scholar
  14. [14]
    D. Kozen. On the Myhill-Nerode theorem for trees. EATCS Bulletin, 47:170–173, June 1992.zbMATHGoogle Scholar
  15. [15]
    W. Kuich. Formal power series over trees. In S. Bozapalidis, editor, Proc. of the 3rd International Conference Developments in Language Theory, pages 61–101. Aristotle University of Thessaloniki, 1998.Google Scholar
  16. [16]
    W. Kuich and A. Salomaa. Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science, Springer Verlag, 1986.Google Scholar
  17. [17]
    M. Magidor and G. Moran. Finite automata over finite trees. Technical Report 30, Hebrew University, Jerusalem, 1969.Google Scholar
  18. [18]
    M. Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23:269–311 (1–42), 1997.MathSciNetGoogle Scholar
  19. [19]
    M. O. Rabin. Decidability of second-order theories and automata in infinite trees. Transactions of the Amer. Math. Soc., 141:1–35, 1969.zbMATHCrossRefMathSciNetGoogle Scholar
  20. [20]
    M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245–270, 1961.zbMATHCrossRefMathSciNetGoogle Scholar
  21. [21]
    H. Seidl. Finite tree automata with cost functions. Theoret. Comput. Sci., 126:113–142, 1994.zbMATHCrossRefMathSciNetGoogle Scholar
  22. [22]
    J.W. Thatcher and J.B. Wright. Generalized finite automata theory with application to a decision problem of second-order logic. Math. Systems Theory, 2(1):57–81, 1968.CrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Björn Borchardt
    • 1
  1. 1.Faculty of Computer ScienceDresden University of TechnologyDresden

Personalised recommendations