Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we study deterministic linear pushdown tree automata (deterministic L-PDTAs) and some variations. Since recognition of an input tree by a deterministic L-PDTA can be done in linear time, deterministic L-PDTAs are applicable to many kinds of applications. A strict hierarchy will be shown among the classes of tree languages defined by a variety of deterministic L-PDTAs. It will be also shown that deterministic L-PDTAs are weakly equivalent to nondeterministic L-PDTAs.

• （社）電子情報通信学会の論文
• 2009-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

スポンサーリンク