顏嗣鈞臺灣大學：電機工程學研究所蕭聖穎Hsiao, Sheng-YingSheng-YingHsiao2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53106本論文提出覆涵樹狀自動機的概念。覆涵自動機是近年來備受關注的研究領域，我們延伸覆涵的觀念於樹狀自動機上。覆涵樹狀自動機本身就是決定性有限樹狀自動機，我們用它來描述有限樹狀語言，但是將接受樹狀語言的條件放寬。除了欲描述的樹狀有限語言外，覆涵樹狀自動機允許接受其他的項，並要求這些項的高度必須比原樹狀有限語言裡的每個項的高度都還要高。這種特性使得覆涵樹狀自動機擁有比一般樹狀自動機較少狀態的優點。 本論文主要的貢獻在於提出最小化覆涵樹狀自動機的演算法，而演算法的核心概念建立於狀態間相似關係的基礎之上。此外我們也提出最小化覆涵樹狀自動機的漸進式演算法，使得原來所描述的有限語言能擴大，而原來的最小覆涵樹狀自動機也能即時更新。The thesis proposes the concept of cover tree automata. A cover tree automaton of a finite tree language L is a deterministic finite tree automaton (DFTA) which accepts L and possibly other terms higher than any term in L. We can use the minimal cover tree automaton to describe a finite tree language, which usually has fewer states than the minimal tree automaton exactly accepting it. The idea of cover tree automata is from cover automata used on words, which have received considerable attention in recent years. The main contribution of the work is concerned with the design of an algorithm to build a cover tree automaton, with minimal number of state, of a given finite tree language. The idea behind the algorithm is based on exploring the similarity relation on terms and on states of tree automata. We also give an incremental algorithm of cover tree automata. Given a known cover tree automaton of a finite tree language and a term which would be added to the finite tree language, the incremental algorithm constructs a cover tree automaton of the original finite tree language plus the added term.Abstract (Chinese) i Abstract (English) ii Contents iii List of Figures iv Chapter 1 Introduction 1 Chapter 2 Preliminaries 4 Section 2.1 Terms 4 2.1.1 Terms and Ground Terms 4 2.1.2 Position 5 2.1.3 Subterms 5 2.1.4 Height and Size 5 Section 2.2 Tree Automata 6 2.2.1 NFTA 6 2.2.2 Accepted terms 7 2.2.3 Run 7 2.2.4 DFTA 7 Chapter 3 Similarity Relation 9 Section 3.1 Similarity Relation on Terms and on States 9 Section 3.2 Minimal DFCTA and Similarity Relation 16 Chapter 4 Algorithm of Finding Similarity Relations on States 19 Section 4.1 Properties of Similarity Relation on States 19 Section 4.2 Finding Similarity Relation between States 27 Chapter 5 Algorithm of Minimizing Cover Tree Automata 30 Section 5.1 Minimizing Algorithm 30 Section 5.2 Properties of Similarity Relation on Terms 31 Section 5.3 Similarity Sequences and Similarity Sets 32 Section 5.4 Correctness of the Minimizing Algorithm 36 Chapter 6 Incremental Algorithm for Minimizing Cover Tree Automata 40 Section 6.1 The Height of Added Term Equal or Lower than the Highest Term 41 Section 6.2 The Height of Added Term larger than the Highest Term 52 Chapter 7 Conclusion 58 References 591350952 bytesapplication/pdfen-US覆涵樹狀自動機最小化漸進式演算法cover automatacover tree automataincremental algorithmminimizing algorithmtree automatathesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53106/1/ntu-95-R93921036-1.pdf