Accession Number:

ADA010088

Title:

On the Complexity of Finite, Pushdown, and Stack Automata.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

• Hunt,H. B. , III

Report Date:

1975-03-01

Pagination or Media Count:

58.0

Abstract:

The complexity of predicates on the 1-way finite, pushdown, and stack automata languages is studied. Every nontrivial predicate on the 1-way stack languages is shown to require exponential time, when applied to the stack automata, indexed grammars, or OI-macro grammars. Every nontrivial predicate on the context-free languages requires as much time and space as any 2-way pushdown automaton language.

Descriptors:

• *PROGRAMMING LANGUAGES
• *GRAMMARS
• MATHEMATICAL LOGIC
• RECURSIVE FUNCTIONS
• THEOREMS
• CONTEXT FREE GRAMMARS
• CONTEXT SENSITIVE GRAMMARS

Subject Categories:

• Linguistics
• Theoretical Mathematics
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE