Accession Number : AD0726393

Title :   Some Results in Tree Automata.

Descriptive Note : Technical rept.,

Corporate Author : MOORE SCHOOL OF ELECTRICAL ENGINEERING PHILADELPHIA PA

Personal Author(s) : Levy,L. S. ; Joshi,A. K.

Report Date : 1971

Pagination or Media Count : 16

Abstract : 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 Arden's transformation or Greibach's 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)

Descriptors :   (*ARTIFICIAL INTELLIGENCE, LINGUISTICS), CONTEXT FREE GRAMMARS, SEMANTICS, SET THEORY, SYNTAX

Subject Categories : Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE