Graduate Thesis Or Dissertation
 

The automated inference of tree system

Pubblico Deposited

Contenuto scaricabile

Scarica il pdf
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6395w963n

Descriptions

Attribute NameValues
Creator
Abstract
  • Tree systems are used in syntactic pattern recognition for describing two-dimensional patterns. We extend results on tree automata with the introduction of the subtree-invariant equivalence relation R. R relates two trees when the appearance of one implies the appearance of the other in similar trees. A new state minimizing algorithm for tree automata is formed using R. We also determine a bound for Brainerd's minimization method. We introduce the Group Unordered Tree Automaton (GUTA) which accepts all orientations of open-line patterns described using directed arc primitives. The specification of a GUTA includes an unordered tree automaton M, which only accepts a standard orientation of a given class of open-line pictures, and a transformation group, which describes how the primitives transform under rotational shifts. The GUTA performs all orientational parses in parallel, reports all successful transformations and operates in the same time complexity as M. The GUTA is much easier to specify than the equivalent non-decomposed unordered tree automaton. The problem of automating the design of unordered and ordered tree automata (grammars) is studied both on a system directed and on a highly interactive level. The system directed method uses Pao's lattice technique to infer tree automata (grammars) from structurally complete samples. It is shown that the method can infer any context-free grammar when provided with skeletal structure descriptions. This extends the results of Pao which only deal with proper subclasses of context-free grammars. The highly interactive inference system is based on the use of tree derivatives, also introduced in this thesis, for determining automaton states and possible state merging. Tree derivatives are sets of tree forms derived by replacing selected subtrees with marked nodes. The derivative sets are used to determine subtree-invariant equivalence relations which characterize tree automata. A minimization algorithm based on tree derivatives is given. We use tree derivatives to prove that a tree automaton with n states can be fully characterized by the set of trees that it accepts of depth at most 2n. The inference method compares tree derivative sets and infers subtree-invariant equivalence relations. A relation is inferred if there is sufficient overlap between the derivative sets. Our method was compared to other tree automata inference schemes, including Crespi-Reghizzi's algorithm. We have shown that our method is applicable to the entire class of context-free grammars and requires a smaller sample than Crespi-Reghizzi's algorithm which can only infer a proper subclass of operator precedence grammars. Furthermore, it appears more general than the other inference systems for tree automata or grammars.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Dichiarazione dei diritti
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Le relazioni

Parents:

This work has no parents.

In Collection:

Elementi

Thumbnail Titolo Data caricata Visibilità Azioni
file details LevineBarryArthur1979.pdf 2017-08-07 Pubblico Scaricare