Graduate Thesis Or Dissertation
 

A generalization of tree automata and its relation to matrix grammars

公开 Deposited

可下载的内容

下载PDF文件
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/nv935671s

Descriptions

Attribute NameValues
Creator
Abstract
  • In this thesis we introduce alpha and beta tree acceptors, generalizations of tree automata. The alpha tree acceptors recognize a tree by final symbol and the beta tree acceptors by final state. We show that alpha and beta tree acceptors recognize the same sets of Gorn trees and demonstrate that there are sets of Gorn trees not recognizably by any alpha tree acceptor. The tree automata are equivalent to the one state alpha tree acceptors. We show that the languages of alpha tree acceptors are exactly those of matrix grammars and the derivation trees of matrix grammars are recognized by alpha tree acceptors. Finally we show that nondeterministic alpha tree acceptors are no more powerful than deterministic alpha tree acceptors.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
权利声明
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.
Replaces

关联

Parents:

This work has no parents.

属于 Collection:

单件

缩略图 标题 上传日期 公开度 行动
file details VomocilDavid1976.pdf 2017-08-23 公开 下载