Logical Complexity of Some Classes of Tree Languages Generated by Multiple-Tree-Automata
✍ Scribed by Wojciech Buszkowski
- Publisher
- John Wiley and Sons
- Year
- 1980
- Tongue
- English
- Weight
- 515 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
LOGICAL COMPLEXITY O F SOME CLASSES O F TREE LANGUAGES GENERATED BY MULTIPLE-TREE-AUTOMATA by WOJCIECH BUSZKOWSKI in Poznaii (Poland) 0. Introduction. Preliminary terminology and notation Multiple-tree-automata (MTAs) correspond to the kind of grammars called Lindenmayer systems with tables (cf. ROZENBERG and SALOMAA [l]). Some results about MTAs were communicated by M. KARPITSSKI and R. DANECRI in lectures talked by them during the International Conference -Fundamentals of Computation Theory -Poznan 1977.
We study here MTAs working on three kinds of trees: finite, infinite, and almost homogenous ones. We establish the logical complexity of classes of languages containing all MTAs behaviors and closed under Boolean operations and projection. Undecidability of the emptiness problem for arbitrary families of automata generating these classes and effectively closed under mentioned operations is proved. We define generalized multiple-tree-automata which extend MTAs and generate exactly the smallest classes of tree languages with considered closure properties.
The author is very indebted to Professor MAREK KARPI~SKI for the conception of problems studied here and stimulation of this work.
We use here a standard terminology and notation of set theory, logic (cf. ROGERS [S]) and automata theory (cf. RABIN [S]). Several particularities and exceptions \I ill be noted below.
T denotes the full binary tree. X , Y , Z, range through subsets of T and are also used aa set-variables in monadic theories. z is reseryed for paths of T . Finite binary sequences (and also individual variables in monadic theories) are denoted by T , y, Z.
if, 5 design strings of respecti4e variables. 5 y (x < y) means that .2: is an initial (a proper initial) segment of y. 1x1, $0, 51 are the lenght of x, the left and the right successors of x respectively. A denotes the empty sequence. t , t' are variables for finite trees. A finite tree t is a finite initial segment of T satisfying the condition (1) _t denotes the frontier of t defined as'follows: