Вестник БФУ им. И. Канта

2012 Выпуск №10

Назад к списку Скачать статью

Формальные языки и автоматы VII: формальные ряды деревьев (Часть II)

Страницы / Pages
7-49

Аннотация

Это восьмая статья в серии, дающей обзор некоторых разделов теории формальных языков и автоматов с использованием полуколец, формальных степенных рядов, матриц и теории неподвижных точек. Рассматриваются автоматы над деревьями (рядами деревьев) и системы уравнений над рядами деревьев. Основные темы статьи:
1.    Магазинные автоматы над деревьями, состоянием которых являются ряды деревьев над полукольцом, к тому же алгебраические системы над рядами деревьев эквивалентны; более того, класс алгебраических рядов деревьев характеризуется алгебраическими выражениями рядов деревьев (результат Клини).
2.    Класс распознаваемых рядов деревьев замкнут относительно недетерминированных элементарных трансдукций распознаваемых рядов деревьев.
3.    Семейства распознаваемых и алгебраических рядов деревьев суть полные абстрактные семейства рядов деревьев (полные АРТ-семейства).
4. Макростепенные ряды, любое обобщение индексированных языков и алгебраические степенные ряды суть в точности выходы алгебраических и распознаваемых рядов деревьев соответственно; для макр о степенных рядов также имеет место результат Клини. Выходом полных абстрактных рядов деревьев является полное абстрактное семейство степенных рядов.

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.

Список литературы

1.         Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы I: полукольца Конвея и конечные автоматы // Вестник Кали­нинградского государственного университета. 2003. Вып. 3. С. 7—38.

2.         Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы II: непрерывные полукольца и алгебраические системы // Там же. 2005. Вып. 1-2. С. 19-45.

3.    Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы III: магазинные автоматы и формальные степенные ряды // Вестник Российского государственного университета им. И. Канта. 2006. Вып. 10. С. 8-27.

4.    Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы IV: трансдукторы и абстрактные семейства // Там же. 2008. Вып. 10. С. 6-23.

5.         Алешников С. И., Болтнев Ю. Ф., Език 3. и др. Формальные языки и автоматы V: пары полукольцо-полумодуль Конвея и конечные автоматы // Там же. 2009. Вып. 10. С. 6-41

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. Gecseg F., Steinby M. Tree Automata. Akademiai Kiado, 1984.
31. Gecseg 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.