✦ LIBER ✦

On the Complexity of 2-Monotone Restarting Automata

✍ Scribed by Tomasz Jurdziński; Friedrich Otto; František Mráz; Martin Plátek

Publisher: Springer
Year: 2007
Tongue: English
Weight: 574 KB
Volume: 42
Category: Article
ISSN: 1433-0490
DOI: 10.1007/s00224-007-9004-y

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Hierarchy of Monotone Deterministic No

A Hierarchy of Monotone Deterministic Non-Forgetting Restarting Automata

✍ Hartmut Messerschmidt; Friedrich Otto 📂 Article 📅 2009 🏛 Springer 🌐 English ⚖ 660 KB

A note on the monotone complexity of 2-R

A note on the monotone complexity of 2-REF

✍ Peter Clote 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 523 KB

On the Computational Complexity of P Aut

On the Computational Complexity of P Automata

✍ Erzsébet Csuhaj-Varjú; Oscar H. Ibarra; György Vaszil 📂 Article 📅 2006 🏛 Springer Netherlands 🌐 English ⚖ 296 KB

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 complexity of finite autonomous M

On the complexity of finite autonomous Moore automata

✍ M. Katsura 📂 Article 📅 1987 🏛 Springer Netherlands 🌐 English ⚖ 825 KB

Lower bounds on monotone complexity of t

Lower bounds on monotone complexity of the logical permanent

✍ A. A. Razborov 📂 Article 📅 1985 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 619 KB