Restrictions on Monadic Context-Free Tree Grammars

Restrictions on Monadic Context-Free Tree Grammars Akio Fujiyoshi Department of Computer and Information Sciences, Ibaraki University 4-12-1 Nakanarusawa, Hitachi, Ibaraki, 316-8511, Japan fujiyoshi@cis.ibaraki.ac.jp Abstract In this paper, subclasses of monadic context- free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs gen- erate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and non- deletion on monadic CFTGs are necessary to generate the same class of languages. Epsilon- freeness on linear, nondeleting, monadic CFTG is also examined. 1 Introduction The context-free tree grammars (CFTGs) were in- troduced by W. C. Rounds (1970) as tree gener- ating systems, the definition of which is a direct generalization of context-free grammars (CFGs) from strings to rooted, ordered, labeled trees. For the application of CFTGs to natural languages, many kinds of restrictions on CFTGs have been considered because the string languages generated by CFTGs are exactly indexed languages, whose emptiness problem and uniform membership prob- lem are exponential time complete, i.e., nonre- stricted CFTGs are formidable. One approach to define subclasses of CFTGs is to restrict the ranks of nonterminals. The rank of a nonterminal is a nat- ural number assigned to each nonterminal by which the number of children of the node labeled by the nonterminal is fixed. Through this approach, the simplest model of CFTGs is regular tree grammars (RTGs) (Brainerd, 1969), where the ranks of non- terminals are all 0. The string languages generated by RTGs are the languages generated by context- free grammars (CFGs). Since recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than CFGs, this paper focuses on monadic CFTGs, where the ranks of nonterminals are either 0 or 1. Another formalism of tree generating systems is tree adjoining grammars (TAGs) (Joshi et al., 1975; Joshi and Schabes, 1996; Abeill´e and Rambow, 2000). TAGs have been widely studied relating them to natural languages, and it was shown that TAGs have the same generative power of string lan- guages as other formalisms for natural languages developed independently such as head grammars, combinatory categorial grammars and linear in- dexed grammars (Vijay-Shanker and Weir, 1994). It is also noteworthy that there are recognition algorithms for the string languages generated by TAGs that run in O(n6) and O(M(n2)) time (Ra- jasekaran, 1996; Rajasekaran and Yooseph, 1998). From the view point of CFTG, the languages gener- ated by TAGs were examined (Fujiyoshi and Kasai, 2000; Fujiyoshi, 2004; M¨oennich, 1997), and it was shown that linear, nondeleting, monadic CFTGs generate the same class of string languages as TAGs and a strictly larger class of tree languages than TAGs. Linearity is a restriction on CFTGs that requires the number of occurrences of every vari- able in the right-hand side of a rule be no more than 1, and nondeletion requires all variables in the left-hand side of a rule occur at least once in the right-hand side. In other words, linear, nondelet- …

Content truncated to 500 words