Formal languages and automata VII: Formal tree series (Part I)
- Pages
- 5-32
Abstract
This is the seventh paper of a series of papers that will give a survey on several topics on formal languages and automata by using semirings, formal power series, matrices and xed point theory. The seventh paper of this series deals with tree (series) automata and systems of equations over tree. The main topics of the paper are the following. 1. Tree automata (resp. nite, polynomial tree automata), whose behaviors are tree series over a semiring, and systems of equations (resp. nite, polynomial systems of equations), whose least solutions are tuples of tree series over a semiring, are equivalent. 2. A Kleene result: the class of recognizable tree series is characterized by rational tree series expressions.
Reference
1. Aho A. V. Indexed grammarsan extension of context-free grammars // JACM. 1968. V. 15. P. 647671.
7. Berstel J. Transductions and Context-Free Languages. Teubner, 1979.
8. Berstel J., Reutenauer C. Recognizable formal power series on trees //Theor. Comput. Sci. 1982. Vol. 18. P. 115148.
9. Block R. E., Gri ng G. Recognizable formal series on trees and cofree coalgebraic systems // J. of Algebra 1999. Vol. 215. P. 543573.
10. Bloom St. L., Esik Z. Iteration Theories. EATCS Monographs on Theoretical Computer Science. Springer, 1993.
11. Bozapalidis S. Eective construction of the syntactic algebra of a
recognizable series on trees // Acta Inf. 1991. Vol. 28. P. 351363.
12. Bozapalidis S. Alphabetic tree relations // Theoret. Comput. Sci. 1992.Vol. 99. P. 177211.
13. Bozapalidis S. Convex algebras, convex modules and formal power series on trees // J. Automata, Languages and Combinatorics 1996. Vol. 1.P. 165180.
14. Bozapalidis S. Equational elements in additive algebras // Theory
Comput. Systems 1999. Vol. 32. P. 133.
15. Bozapalidis S. Context-free series on trees // Information and
Computation 2001. Vol. 169. P. 186229.
16. Bozapalidis S., Rahonis G. On two families of forests // Acta Inf. 1994.Vol. 31. P. 235260.
17. Bucher W., Maurer H. Theoretische Grundlagen der Programmiersprachen.B. I. Wissenschaftsverlag, 1984.
18. Comon H., Dauchet M., Gilleron R., Jaquemard F., Lugiez D., Tison S., Tommasi M. Tree Automata-Techniques and Applications. Manuscript.
19. Courcelle B. Equivalences and transformations of regular systemsApplications to recursive program schemes and grammars // Theor. Comp.Sci. 1986. Vol. 42. P. 1122.
20. Engelfriet J. Bottom-up and top-down tree transformationsa comparison // Math. Systems Theory. 1975. Vol. 9. P. 198231.
21. Engelfriet J., Fulop Z., Vogler H. Bottom-up and Top-down Tree Series Transducers // J.Automata, Languages and Combinatorics. 2002. Vol. 7.P. 1170.
22. Engelfriet J., Schmidt E. M. IO and OI. I // J. Comput. Systems Sci.1977. Vol. 15. P. 328353.
23. Esik Z. Completeness of Park induction // Theor. Comput. Sci. 1997.Vol. 177. P. 217283.
24. Ésik Z., Kuich W. Formal tree series // J. Automata, Languages and Combinatorics. 2003. Vol. 8. P. 219285.
25. Fischer M. J. Grammars with macro-like productions // 9th Annual Symposium on Switching and Automata Theory. 1968. P. 131142.
26. Fulop Z., Vogler H. Syntax-Directed Semantics. Springer, 1998.
27. Fulop Z., Vogler H. Tree series transformations that respect copying //Theory of Computing Systems. 2003. Vol. 36. P. 247293.
28. Gecseg F., Steinby M. Tree Automata. Akademiai Kiado, 1984.
29. Gecseg F., Steinby M. Tree Languages / Handbook of Formal
Languages. Springer, 1997. Vol. 3. Chapt. 1. P. 168.
30. Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, 1975.
31. Gratzer G. Universal Algebra. Springer, 1979.
32. Gruska J. A characterization of context-free languages // Journal of Computer and System Sciences. 1971. Vol. 5. P. 353364.
33. Guessarian I. Algebraic Semantics // Lect. Notes Comput. Sci. 1981.Vol. 99.
34. Guessarian I. Pushdown tree automata. Math. Systems Theory. 1983.Vol. 16. P. 237263.
35. Kuich W. Semirings and formal power series: Their relevance to formal languages and automata theory // Handbook of Formal Languages. Springer,1997. Vol. 1. Chapt. 9. P. 609677.
36. Kuich W. Gau¼ian elimination and a characterization of algebraic power series // MFCS 98, Lect. Notes Comput. Sci. 1998. Vol. 1450. P. 512521.
37. Kuich W. Formal power series over trees // Proceedings of the 3rd International Conference Developments in Language Theory. Aristotle University of Thessaloniki, 1998. P. 61101.
38. Kuich W. Tree transducers and formal tree series // Acta Cybernetica.1999. Vol. 14. P. 135149.
39. Kuich W. Full abstract families of tree series I // Jewels are Forever.Springer, 1999. P. 145156.
40. Kuich W. Abstract families of tree series II // Proceedings of the International Workshop on Grammar Systems 2000. Schlesische UniversitatTroppau, 2000. P. 347358.
41. Kuich W. Formal series over algebras // Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893. Springer, 2000. P. 488-496.
42. Kuich W. Pushdown tree automata, algebraic tree systems, and algebraic tree series // Information and Computation. 2001. Vol. 165. P. 6999.
43. Kuich W. Formal power series over sorted algebras // Discrete Math.2002. Vol. 254. P. 231258.
44. Kuich W., Salomaa A. Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science. Vol. 5. Springer, 1986.
45. Lausch H., Nobauer W. Algebra of Polynomials. North-Holland, 1973.
46. Rounds W. C. Trees, transducers and transformations. PhD thesis,Stanford University, 1968.
47. Rounds W. C. Context-free grammars on trees // ACM Symposium on Theory of Computing. 1969. P. 143148.
48. Rounds W. C. Mappings and grammars on trees // Math. Systems Theory. 1970. Vol. 4. P. 257287.
49. Salomaa A. Formal Languages. Academic Press, 1973.
50. Seidl H. Deciding equivalence of nite tree automata // STACS88, Lect.Notes Comput. Sci. 1989. Vol. 349. P. 480492.
51. Thatcher J. W. Generalized2 sequential machine maps. IBM Research Report RC2466, 1969.
52. Thatcher J. W. Generalized sequential machine maps // J. Comp. Syst.Sci. 1970. Vol. 4. P. 339367.
53. Thatcher J. W., Wright J. B. Generalized nite automata theory with an application to a decision problem of second-order logic // Math. Systems Theory. 1968. Vol. 2. P. 5781.
54. Wechler W. Universal Algebra for Computer Scientists. EATCS Monographs on Computer Science, Vol. 25. Springer, 1992.