返回Google圖書搜尋

Some results in tree automata

出版	University of Pennsylvania. Moore School of Electrical Engineering, 1971
URL	http://books.google.com.hk/books?id=oRveXwAACAAJ&hl=&source=gbs_api

註釋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).