Linearity and nondeletion on monadic context-free tree grammars |
| |
| Authors: | Akio Fujiyoshi |
| |
| Affiliation: | Department of Computer and Information Sciences, Ibaraki University, 4-12-1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan |
| |
| Abstract: | In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages. |
| |
| Keywords: | Formal languages Context-free tree grammar Tree adjoining grammar |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
