Accession Number:

AD0680783

Title:

WRITING PUSHDOWN ACCEPTORS,

Descriptive Note:

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1968-05-14

Pagination or Media Count:

79.0

Abstract:

The paper introduces a new automaton, called a writing pushdown acceptor abbreviated wpda, and investigates some of its properties. A wpda is essentially a two-way pushdown acceptor that can write on its input tape. A number of results about wpda are established. In particular, it is shown that 1 Each set accepted by a wpda is accepted by some wpda that halts for all inputs 2 the family of sets accepted by deterministic wpda forms a Boolean algebra of sets, contains the family of context sensitive languages, and properly contains the family of sets accepted by deterministic two-way pushdown acceptors and 3 the family of sets accepted by deterministic wpda is contained in the family of sets accepted by deterministic stack acceptors. In the deterministic case, the containment is shown to be proper. Author

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE