𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On The Space Complexity Of Turn Bounded Pushdown Automata

✍ Scribed by Moriya, Etsuro; Tada, Takemaru

Book ID
127136580
Publisher
Taylor and Francis Group
Year
2003
Tongue
English
Weight
183 KB
Volume
80
Category
Article
ISSN
0020-7160

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Unary Context-Free Grammars and Pushdown
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds
✍ Giovanni Pighizzini; Jeffrey Shallit; Ming-wei Wang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 240 KB

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity poi

On the computational power of pushdown a
On the computational power of pushdown automata
✍ A.V. Aho; J.D. Ullman; J.E. Hopcroft πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 361 KB

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 fini