𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the computational power of pushdown automata

✍ Scribed by A.V. Aho; J.D. Ullman; J.E. Hopcroft

Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
361 KB
Volume
4
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We present a relation between the sets accepted by two-way pushdown automata and certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a finite number of n, T uses no more than log~tn storage cells when given an input of length n, then L is accepted by a twoway nondeterministic pushdown automaton. Thus, any nondeterministic tape complexity class L(n) such that sup,~ (L(n)/log n)) = 0 is a subfamily of the two-way nondeterministic pushdown automaton languages.

I. DEFINITIONS

We shall begin by giving formal definitions of the two-way pushdown automaton and off-line Turing machine. A two-way nondeterministicpushdown automaton (2NPDA) [1,2] is an 8-tuple P = (K, Z, F, 8, q0, Z0, $, F), where K, 27, and F are, respectively, finite sets of states, input symbols, and tape symbols. F C_ K is the set of final states; q0 in K is the start state; Z o in /" is the start symbol

πŸ“œ SIMILAR VOLUMES

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
✍ K. Sutner πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N

On computing the entropy of cellular aut
On computing the entropy of cellular automata
✍ Michele D'amico; Giovanni Manzini; Luciano Margara πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 208 KB

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X; F) is a measure of the complexity of the dynamics of F over the space X . The problem of computing (or even approximating) the topological entropy of a gi

The size of power automata
The size of power automata
✍ K. Sutner πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 179 KB

We describe a class of simple transitive semiautomata that exhibit full exponential blow-up during deterministic simulation. For arbitrary semiautomata we show that it is PSPACE-complete to decide whether the size of the accessible part of their power automata exceeds a given bound. We comment on th