Some Results in Tree Automata.
MOORE SCHOOL OF ELECTRICAL ENGINEERING PHILADELPHIA PA
Pagination or Media Count:
The following three results concerning tree automata are presented in this paper Rounds has presented the following open problem For every recognizable set R, can one construct a deterministic finite state transformation recognizing R. The authors show that this is not possible, in fact, even for a local set. However, the following is true For every recognizable set, R, there is an inverse projection, R primed effectively obtained, such that R primed is recognized by a deterministic finite state transformation. Martin and Vere in their study of tree automata leave open the question of whether Generalized Syntax Directed Transductions are closed under Ardens transformation or Greibachs transformation, and conjecture that they are not. The authors prove that this conjecture is true. Peters and Ritchie have shown that if in a grammar where the generative rules are context-free, there are recognition rules which are context sensitive, the language recognized is still context free. A tree automata oriented proof is given by Rounds. The authors show that a similar result holds also for right linear grammars. Author