Multi-Phase Tree Transformations
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we introduce a computational model of a tree transducer called a bi-stage transducer and study its properties. We consider a mapping on trees realized by composition of any sequence of top-down transducers and bottom-up transducers, and call such a mapping a multi-phase tree transformation. We think a multi-phase tree transformation is sufficiently powerful. It is shown that in the case of rank-preserving transducers, a multi-phase tree transformation is realized by a bi-stage transducer.
- 社団法人電子情報通信学会の論文
- 1997-04-25
著者
-
Fujiyoshi Akio
Department Of Computer And Information Sciences Ibaraki University
-
Fujiyoshi Akio
Department Of The Computer Science And Information Mathematics University Of Electro-communications
-
KASAI Takumi
Department of the Computer Science and Information Mathematics, University of Electro-Communications
-
Kasai Takumi
Department Of Computer Science University Of Electro-communications
-
Kasai Takumi
Department Of The Computer Science And Information Mathematics University Of Electro-communications
関連論文
- 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)
- Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete
- Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata