Application of the CKY Algorithm to Recognition of Tree Structures for Linear, Monadic Context-Free Tree Grammars


IEICE TRANSACTIONS on Information and Systems   Vol.E90-D   No.2   pp.388-394
Publication Date: 2007/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e90-d.2.388
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Formal Languages
formal languages,  recognition algorithm,  spine grammar,  tree adjoining grammar,  context-free tree grammar,  

Full Text: PDF>>
Buy this Article

In this paper, a recognition algorithm for the class of tree languages generated by linear, monadic context-free tree grammars (LM-CFTGs) is proposed. LM-CFTGs define an important class of tree languages because LM-CFTGs are weakly equivalent to tree adjoining grammars (TAGs). The algorithm uses the CKY algorithm as a subprogram and recognizes whether an input tree can be derived from a given LM-CFTG in O(n4) time, where n is the number of nodes of the input tree.