Alternating Pushdown and Stack Automata

Authors:
  • RLRichard E. Ladner
    Richard E. Ladner
  • RLRichard J. Lipton
    Richard J. Lipton
  • LSLarry J. Stockmeyer
    Larry J. Stockmeyer

Abstract
The classes of languages accepted by alternating pushdown automata, alternating stack automata, and alternating nonerasing stack automata, both with and without an auxiliary space bounded worktape, are characterized in terms of complexity classes defined by time bounded deterministic Turing machines. It is also shown that alternating 2-way finite state machines accept only regular languages.

This publication has 18 references indexed in Scilit: