A generalization of tree automata and its relation to matrix grammars Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/nv935671s

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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 Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
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
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2014-02-25T21:38:35Z (GMT) No. of bitstreams: 1 VomocilDavid1976.pdf: 607475 bytes, checksum: 71fe66e8e90f800ace6169fb01b4b4b5 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-11-08T16:31:06Z (GMT) No. of bitstreams: 1 VomocilDavid1976.pdf: 607475 bytes, checksum: 71fe66e8e90f800ace6169fb01b4b4b5 (MD5)
  • description.provenance : Made available in DSpace on 2014-02-25T21:38:35Z (GMT). No. of bitstreams: 1 VomocilDavid1976.pdf: 607475 bytes, checksum: 71fe66e8e90f800ace6169fb01b4b4b5 (MD5) Previous issue date: 1975-05-22
  • description.provenance : Submitted by Georgeann Booth (gbscannerosu@gmail.com) on 2013-11-07T01:35:16Z No. of bitstreams: 1 VomocilDavid1976.pdf: 607475 bytes, checksum: 71fe66e8e90f800ace6169fb01b4b4b5 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items