Accession Number:

AD0701753

Title:

TREE ACCEPTORS AND SOME OF THEIR APPLICATIONS

Descriptive Note:

Technical memo.

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CA

Personal Author(s):

• Doner, John

Report Date:

1967-07-24

Pagination or Media Count:

86.0

Abstract:

The paper concerns a generalization of a part of finite automata theory. It defines a generalized finite automaton, called a tree acceptor, which has as its inputs finite trees of symbols instead of the usual sequences of symbols. Ordinary finite automata prove to be special cases of tree acceptors. It turns out that many of the results of finite automata theory remain valid in their appropriately generalized forms. The definitions of trees and tree acceptors are given, and some of their basic properties are developed. The properties of the sets of trees accepted by tree acceptors are investigated and an alternative characterization of those sets is obtained. An application of these results to the theory of context-free languages is given. A positive solution to a problem of Buchi is found. Is the weak second-order theory of two successors decidable. This result is applied to decision problems of weak second-order logic. A result of Buchi and the generalized products of Feferman and Vaught are utilized to extend the decidability result to a more general case The weak second-order theory of locally free algebras with only unary operations.

Descriptors:

• *PROGRAMMING LANGUAGES
• AUTOMATA
• COMPUTATIONAL LINGUISTICS
• CONTEXT FREE GRAMMARS
• MATHEMATICAL LOGIC
• SET THEORY
• THEOREMS
• THEORY

Subject Categories:

• Computer Programming and Software
• Bionics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE