Sublinear-Time Probabilistic Cellular Automata

Author Augusto Modanese



PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.47.pdf
  • Filesize: 0.88 MB
  • 22 pages

Document Identifiers

Author Details

Augusto Modanese
  • Aalto University, Espoo, Finland

Acknowledgements

I would like to thank Thomas Worsch for the helpful discussions and feedback as well as the anonymous reviewers for their insightful comments.

Cite AsGet BibTex

Augusto Modanese. Sublinear-Time Probabilistic Cellular Automata. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.47

Abstract

We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes RP and BPP) and establish a separation between the classes of languages they can recognize all the way up to o(√n) time. As a consequence, we have a Ω(√n) lower bound for derandomizing constant-time one-sided error PACAs (using deterministic ACAs). We also prove that derandomization of T(n)-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of T(n) = ω(log n) implies non-trivial derandomization results for the class RP (e.g., P = RP). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages (LLT) and prove that the languages decidable by constant-time two-sided error PACAs are "sandwiched" in-between the closure of LLT under union and intersection and the class of locally threshold testable languages (LTT).

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Cellular automata
  • local computation
  • probabilistic models
  • subregular language classes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  2. Pablo Arrighi, Nicolas Schabanel, and Guillaume Theyssier. Stochastic cellular automata: Correlations, decidability and simulations. Fundam. Informaticae, 126(2-3):121-156, 2013. URL: https://doi.org/10.3233/FI-2013-875.
  3. Danièle Beauquier and Jean-Eric Pin. Factors of words. In Automata, Languages and Programming, 16th International Colloquium, ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings, pages 63-79, 1989. URL: https://doi.org/10.1007/BFb0035752.
  4. Marianne Delorme and Jacques Mazoyer, editors. Cellular Automata. Number 460 in Mathematics and Its Applications. Springer Netherlands, 1999. URL: https://doi.org/10.1007/978-94-015-9153-9.
  5. Pedro García and José Ruiz. Threshold locally testable languages in strict sense. In Carlos Martín-Vide and Victor Mitrana, editors, Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back: Essays in Honour of Gheorghe Paun, volume 9 of Topics in Computer Mathematics, pages 243-252. Taylor and Francis, 2003. Google Scholar
  6. Oded Goldreich. Computational Complexity: A Conceptional Perspective. Cambridge University Press, 2008. Google Scholar
  7. William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success RL. SIAM J. Comput., 49(4):811-820, 2020. URL: https://doi.org/10.1137/19M1268707.
  8. Oscar H. Ibarra, Michael A. Palis, and Sam M. Kim. Fast parallel language recognition by cellular automata. Theor. Comput. Sci., 41:231-246, 1985. URL: https://doi.org/10.1016/0304-3975(85)90073-8.
  9. Sam Kim and Robert McCloskey. A characterization of constant-time cellular automata computation. Phys. D, 45(1-3):404-419, 1990. URL: https://doi.org/10.1016/0167-2789(90)90198-X.
  10. Martin Kutrib. Cellular automata and language theory. In Encyclopedia of Complexity and Systems Science, pages 800-823. Springer, 2009. URL: https://doi.org/10.1007/978-0-387-30440-3_54.
  11. Jean Mairesse and Irène Marcovici. Around probabilistic cellular automata. Theor. Comput. Sci., 559:42-72, 2014. URL: https://doi.org/10.1016/j.tcs.2014.09.009.
  12. Robert McNaughton and Seymour Papert. Counter-Free Automata. The MIT Press, 1971. Google Scholar
  13. Augusto Modanese. Lower bounds and hardness magnification for sublinear-time shrinking cellular automata. In Rahul Santhanam and Daniil Musatov, editors, Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pages 296-320. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79416-3_18.
  14. Augusto Modanese. Sublinear-time language recognition and decision by one-dimensional cellular automata. Int. J. Found. Comput. Sci., 32(6):713-731, 2021. URL: https://doi.org/10.1142/S0129054121420053.
  15. Augusto Modanese. Sublinear-time probabilistic cellular automata. CoRR, abs/2203.14614, 2022. URL: http://arxiv.org/abs/2203.14614.
  16. Noam Nisan. Pseudorandom generators for space-bounded computation. Comb., 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  17. José Ruiz, Salvador España Boquera, and Pedro García. Locally threshold testable languages in strict sense: Application to the inference problem. In Grammatical Inference, 4th International Colloquium, ICGI-98, Ames, Iowa, USA, July 12-14, 1998, Proceedings, pages 150-161, 1998. URL: https://doi.org/10.1007/BFb0054072.
  18. Rudolph Sommerhalder and S. Christian van Westrhenen. Parallel language recognition in constant time by cellular automata. Acta Inf., 19:397-407, 1983. URL: https://doi.org/10.1007/BF00290736.
  19. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1-24:40, 2013. URL: https://doi.org/10.1145/2431211.2431223.
  20. Véronique Terrier. Language recognition by cellular automata. In Handbook of Natural Computing, pages 123-158. Springer, 2012. URL: https://doi.org/10.1007/978-3-540-92910-9_4.
  21. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  22. Andrew Chi-Chih Yao. Circuits and local computation. In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 186-196. ACM, 1989. URL: https://doi.org/10.1145/73007.73025.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail