Формальные языки и автоматы VII: формальные ряды деревьев (Часть II)
Аннотация
Это восьмая статья в серии, дающей обзор некоторых разделов теории формальных языков и автоматов с использованием полуколец, формальных степенных рядов, матриц и теории неподвижных точек. Рассматриваются автоматы над деревьями (рядами деревьев) и системы уравнений над рядами деревьев. Основные темы статьи:
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.