The Relation between Unary Parameter Macro Tree Transducers and Spine Grammars

スポンサーリンク

概要

• 論文の詳細を見る

• Spine grammars are restricted contest-free tree grammars, and it is known that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. It has been shown that linear pushdown tree automata accept exactly the same as the class of tree languages generated by spine grammars; however, the relation between spine grammars and tree transducers has not been investigated. In this paper, we show that the class of tree languages generated by spine grammars is the same as the class of surface sets generated by total deterministic, linear, nondeleting, unary parameter macro tree transducers.

• 社団法人電子情報通信学会の論文
• 2002-02-01

著者

• Fujiyoshi Akio

  Department Of Computer And Information Sciences Ibaraki University

関連論文

• 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

スポンサーリンク