Minimizing Cover Tree Automata
Date Issued
2006
Date
2006
Author(s)
Hsiao, Sheng-Ying
DOI
en-US
Abstract
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.
Subjects
覆涵樹狀自動機
最小化
漸進式演算法
cover automata
cover tree automata
incremental algorithm
minimizing algorithm
tree automata
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93921036-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):a0e41fbe3d55facd05c7f93464750a3b