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

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.

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1975
Accession Number
ADA010088

Entities

People

  • H. B. Hunt Iii

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Automata
  • Grammars
  • Language
  • Linguistics

Readers

  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space