Comments on Complete Sets of Tree Automata

  • Ferenc Gécseg
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Products of tree automata do not preserve the basic properties of homomorphically and metrically complete systems of finite state automata. To remedy it, we have introduced the concept of the quasi-product of tree automata which is only a slightly more general than the product. In this paper we present the main properties of the quasi-product concerning homomorphic and metric representation of tree automata, and compare the representing powers of special quasi-products.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Ésik, Z.: Definite tree automata and their cascade compositions. Publ. Math. 48 (1996), 243–261.zbMATHGoogle Scholar
  2. 2.
    Fülöp, Z., Vogler, H.: Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer-Verlag, 1998.Google Scholar
  3. 3.
    Gécseg, F.: On R-products of automata I. Studia Sci. Math. Hungar. 1 (1966), 437–441.MathSciNetGoogle Scholar
  4. 4.
    Gécseg, F.: Metrically complete systems of automata (Russian). Kibernetika (Kiev) 3 (1968), 96–98.Google Scholar
  5. 5.
    Gécseg, F.: On a representation of deterministic frontier-to-root tree transformations. Acta Sci. Math. 45 (1983), 177–187.zbMATHGoogle Scholar
  6. 6.
    Gécseg, F.: Products of automata. Springer-Verlag, 1986.Google Scholar
  7. 7.
    Gécseg, F.: Homomorphic representations by products of tree automata. In: Results and Trends in Theoretical Computer Science (Proceedings, Colloquium in Honour of Arto Salomaa, Graz, 1994), Lecture Notes in Computer Science, Vol. 812, Springer-Verlag, 1994, 131–139.Google Scholar
  8. 8.
    Gécseg, F.: On quasi-products of tree automata. J.UCS 2 (2002), 184–192.Google Scholar
  9. 9.
    Gécseg, F., Imreh, B.: On complete sets of tree automata. In: Third International Conference Developments in Language Theory (Thessaloniki, 1997), 37–47.Google Scholar
  10. 10.
    Letičevskii, A. A.: A condition for the completeness of finite automata (Russian). Žurn. vyčisl. matem. i matem. fiz. 1 (1961), 702–710.Google Scholar
  11. 11.
    Ricci, W.: Cascades of tree automata and computations in universal algebra. Math. Systems Theory 7 (1973), 201–218.zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Steinby, M.: On the structure and realization of tree automata. In: Second Coll. sur les Arbres en Algèbre et en Programmation (Lille, 1977), 235–248.Google Scholar
  13. 13.
    Virágh, J.: Deterministic ascending tree automata II. Acta Cybernet. 6 (1983), 291–301.zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Ferenc Gécseg
    • 1
  1. 1.University of SzegedSzegedHungary

Personalised recommendations