Application of the CKY Algorithm to Recognition of Tree Structures for Linear, Monadic Context-Free Tree Grammars(Formal Languages,<Special Section>Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
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(n^4) time, where n is the number of nodes of the input tree.
- 社団法人電子情報通信学会の論文
- 2007-02-01
著者
-
Fujiyoshi Akio
The Department Of Computer And Information Sciences Ibaraki University
-
Fujiyoshi Akio
Department Of Computer And Information Sciences Ibaraki University
-
Fujiyoshi Akio
Ibaraki Univ. Hitachi‐shi Jpn
関連論文
- Minimum Spanning Tree Problem with Label Selection
- The Relation between Unary Parameter Macro Tree Transducers and Spine Grammars
- Multi-Phase Tree Transformations
- Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars(Automata and Formal Language Theory)
- Application of the CKY Algorithm to Recognition of Tree Structures for Linear, Monadic Context-Free Tree Grammars(Formal Languages,Foundations of Computer Science)
- Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata