2012 Issue №10

Formal languages and automata VII: Formal tree series (Part II)

Pages

7-49

Abstract

This is the eighth 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. Pushdown tree automata, whose behaviors are tree series over a semiring, and algebraic tree systems are equivalent; moreover, the class of algebraic tree series is characterized by algebraic tree series expressions (a Kleene result). 2. The class of recognizable tree series is closed under nondeterðministic simple recognizable tree series transductions.3. The families of recognizable tree series and of algebraic tree series are full abstract families of tree series (full AFTs). 4. The macro power series, a generalization of the indexed languages, and the algebraic power series are exactly the yields of algebraic tree series and of recognizable tree series, respectively; there is a Kleene result for macro power series; the yield of a full AFT is a full abstract family of power series.

Reference

6.    Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы VI: ш-алгебраические системы и трансдукторы // Там же. 2010. С. 8-32.

7.    Алешников СИ., Болтнев Ю.Ф., Език 3. и др. Формальные языки и автоматы VII: формальные ряды деревьев (Часть I) // Вестник Балтий­ского федерального университета им. И.Канта. Вып. 10. 2011. С. 5—32.

8. Aho A. V. Indexed grammarsan extension of context-free grammars //JACM. 1968. Vol. 15. P. 647671.
9. Berstel J. Transductions and Context-Free Languages. Teubner, 1979.
10. Berstel J., Reutenauer C. Recognizable formal power series on trees //Theor. Comput. Sci. 1982. Vol. 18. P. 115148.
11. Block R. E., Gring G. Recognizable formal series on trees and cofree coalgebraic systems // J. of Algebra. 1999. Vol. 215. P. 543573.
12. Bloom St. L.,
Esik Z. Iteration Theories. EATCS Monographs on Theoretical Computer Science. Springer, 1993.
13. Bozapalidis S. Eective construction of the syntactic algebra of a recognizable series on trees // Acta Inf. 1991. Vol. 28. P. 351363.
14. Bozapalidis S. Alphabetic tree relations // Theoret. Comput. Sci. 1992.Vol. 99. P. 177211.
15. Bozapalidis S. Convex algebras, convex modules and formal power series on trees // J. Automata, Languages and Combinatorics. 1996. Vol. 1.P. 165180.
16. Bozapalidis S. Equational elements in additive algebras // Theory Comput. Systems. 1999. Vol. 32. P. 133.
17. Bozapalidis S. Context-free series on trees // Information and Computation. 2001. Vol. 169. P. 186229.
18. Bozapalidis S., Rahonis G. On two families of forests // Acta Inf. 1994. Vol. 31. P. 235260.
19. Bucher W., Maurer H. Theoretische Grundlagen der Programmiersprachen.B. I. Wissenschaftsverlag, 1984.
20. Comon H., Dauchet M., Gilleron R. et al Tree Automata-Techniques and Applications. Manuscript.
21. Courcelle B. Equivalences and transformations of regular systemsApplications to recursive program schemes and grammars // Theor. Comp.Sci. 1986. Vol. 42. P. 1122.
22. Engelfriet J. Bottom-up and top-down tree transformationsa comparison // Math. Systems Theory. 1975. Vol. 9. P. 198231.
23. Engelfriet J., Fulop Z., Vogler H. Bottom-up and Top-down Tree Series Transducers // J. Automata, Languages and Combinatorics. 2002. Vol. 7.P. 1170.
24. Engelfriet J., Schmidt E. M. IO and OI // I. J. Comput. Systems Sci.1977. Vol. 15. P. 328353.
25.
Esik Z. Completeness of Park induction // Theor. Comput. Sci. 1997.Vol. 177. P. 217283.
26.
Esik Z., Kuich W. Formal tree series // J. Automata, Languages and Combinatorics. 2003. Vol. 8. P. 219285.
27. Fischer M. J. Grammars with macro-like productions // 9th Annual Symposium on Switching and Automata Theory. 1968. P. 131142.
28. Fulop Z., Vogler H. Syntax-Directed Semantics. Springer, 1998.
29. Fulop Z., Vogler H. Tree series transformations that respect copying //Theory of Computing Systems. 2003. Vol. 36. P. 247293.
30. G
ecseg F., Steinby M. Tree Automata. Akademiai Kiado, 1984.
31. G
ecseg F., Steinby M. Tree Languages // Handbook of Formal Languages. Springer, 1997. Vol. 3. Chapter 1. P. 168.

32. Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, 1975.
33. Gratzer G. Universal Algebra. Springer, 1979.
34. Gruska J. A characterization of context-free languages // Journal of Computer and System Sciences. 1971. Vol. 5. P. 353364.
35. Guessarian I. Algebraic Semantics // Lect. Notes Comput. Sci. Vol. 99.Springer, 1981.
36. Guessarian I. Pushdown tree automata // Math. Systems Theory. 1983.Vol. 16. P. 237263.
37. Kuich W. Semirings and formal power series: Their relevance to formal languages and automata theory // Handbook of Formal Languages. Springer,1997. Vol. 1. Chapter 9. P. 609677.
38. Kuich W. Gau¼ian elimination and a characterization of algebraic power series // MFCS98, Lect. Notes Comput. Sci. 1998. Vol. 1450. P. 512521.
39. Kuich W. Formal power series over trees // Proceedings of the 3rd International Conference Developments in Language Theory. Aristotle University of Thessaloniki, 1998. P. 61101.
40. Kuich W. Tree transducers and formal tree series // Acta Cybernetica.1999. Vol. 14. P. 135149.
41. Kuich W. Full abstract families of tree series I //. Jewels are Forever.Springer, 1999. P. 145156.
42. Kuich W. Abstract families of tree series II // Proceedings of the International Workshop on Grammar Systems 2000. Schlesische UniversitatTroppau, 2000. P. 347358.
43. Kuich W. Formal series over algebras // Proceedings of MFCS 2000,Lect. Notes Comput. Sci. Springer, 1893. Vol. 2000. P. 488-496.
44. Kuich W. Pushdown tree automata, algebraic tree systems, and algebraic tree series // Information and Computation. 2001. Vol. 165. P. 6999.
45. Kuich W. Formal power series over sorted algebras // Discrete Math.2002. Vol. 254. P. 231258.
46. Kuich W., Salomaa A. Semirings, Automata, Languages // EATCS Monographs on Theoretical Computer Science. Vol. 5. Springer, 1986.
47. Lausch H., Nobauer W. Algebra of Polynomials. North-Holland, 1973.
48. Rounds W. C. Trees, transducers and transformations. PhD thesis.Stanford University, 1968.
49. Rounds W. C. Context-free grammars on trees // ACM Symposium on Theory of Computing, 1969. P. 143148.
50. Rounds W. C. Mappings and grammars on trees // Math. Systems Theory. 1970. Vol. 4. P. 257287.
51. Salomaa A. Formal Languages. Academic Press, 1973.
52. Seidl H. Deciding equivalence of nite tree automata // STACS88, Lect.Notes Comput. Sci. 1989. Vol. 349. P. 480492.
53. Thatcher J. W. Generalized2 sequential machine maps. IBM Research Report RC2466, 1969.
54. Thatcher J. W. Generalized sequential machine maps // J. Comp. Syst.Sci. 1970. Vol. 4. P. 339367.
55. 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.
56. Wechler W. Universal Algebra for Computer Scientists // EATCS Monographs on Computer Science. Vol. 25. Springer, 1992.