DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA010088
Title:
On the Complexity of Finite, Pushdown, and Stack Automata.
Corporate Author:
WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
Report Date:
1975-03-01
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.
Descriptive Note:
Technical summary rept.,
Pages:
0058
Contract Number:
DA-31-124-ARO-D-462
Contract Number 2:
NSF-GJ-35570
File Size:
0.00MB
