𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Computational Complexity of P Automata

✍ Scribed by Erzsébet Csuhaj-Varjú; Oscar H. Ibarra; György Vaszil

Publisher
Springer Netherlands
Year
2006
Tongue
English
Weight
296 KB
Volume
5
Category
Article
ISSN
1567-7818

No coin nor oath required. For personal study only.

📜 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 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