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):
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:
Subject Categories:
- Linguistics
- Theoretical Mathematics
- Computer Programming and Software