LIPIcs.MFCS.2020.30.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Randomization in Non-Uniform Finite Automata
Authors
-
Part of:
Volume:
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-18
Cite As Get BibTex
Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith. Randomization in Non-Uniform Finite Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.30
Abstract
The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.
Subject Classification
ACM Subject Classification
- Theory of computation → Automata extensions
Keywords
- finite automata
- non-uniform computation
- randomization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Leonard M. Adleman. Two theorems on random polynomial time. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 75-83. IEEE Computer Society, 1978. URL: https://doi.org/10.1109/SFCS.1978.37.
- Allan Borodin. On relating time and space to size and depth. SIAM J. Comput., 6(4):733-744, 1977. URL: https://doi.org/10.1137/0206054.
- Carsten Damm and Markus Holzer. Automata that take advice. In Jirí Wiedermann and Petr Hájek, editors, Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings, volume 969 of Lecture Notes in Computer Science, pages 149-158. Springer, 1995. URL: https://doi.org/10.1007/3-540-60246-1_121.
- Pavol Duris, Rafael Korbas, Rastislav Královic, and Richard Královic. Determinism and nondeterminism in finite automata with advice. In Hans-Joachim Böckenhauer, Dennis Komm, and Walter Unger, editors, Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, volume 11011 of Lecture Notes in Computer Science, pages 3-16. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98355-4_1.
- Patrick C. Fischer and Arnold L. Rosenberg. Multitape one-way nonwriting automata. J. Comput. Syst. Sci., 2(1):88-101, 1968. URL: https://doi.org/10.1016/S0022-0000(68)80006-6.
- Rusins Freivalds. Probabilistic two-way machines. In Jozef Gruska and Michal Chytil, editors, Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31 - September 4, 1981, Proceedings, volume 118 of Lecture Notes in Computer Science, pages 33-45. Springer, 1981. URL: https://doi.org/10.1007/3-540-10856-4_72.
- Rusins Freivalds. Amount of nonconstructivity in deterministic finite automata. Theor. Comput. Sci., 411(38-39):3436-3443, 2010. URL: https://doi.org/10.1016/j.tcs.2010.05.038.
- John Gill. Computational complexity of probabilistic turing machines. SIAM J. Comput., 6(4):675-695, 1977. URL: https://doi.org/10.1137/0206049.
- Oscar H. Ibarra and Bala Ravikumar. Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties. Mathematical Systems Theory, 21(1):1-17, 1988. URL: https://doi.org/10.1007/BF02088003.
- H. Jung. Relationships between probabilistic and deterministic tape complexity. In Jozef Gruska and Michal Chytil, editors, Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31 - September 4, 1981, Proceedings, volume 118 of Lecture Notes in Computer Science, pages 339-346. Springer, 1981. URL: https://doi.org/10.1007/3-540-10856-4_101.
-
Richard M. Karp and Richard J. Lipton. Turing machines that take advice. Enseignement Mathématique, 28(2):191-209, 1982.
- Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Comput. Complex., 8(1):21-49, 1999. URL: https://doi.org/10.1007/s000370050018.
- Ugur Küçük, A. C. Cem Say, and Abuzer Yakaryilmaz. Finite automata with advice tapes. Int. J. Found. Comput. Sci., 25(8):987-1000, 2014. URL: https://doi.org/10.1142/S012905411440019X.
-
Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
- Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. URL: https://doi.org/10.1016/S0019-9958(63)90290-0.
- Kohtaro Tadaki, Tomoyuki Yamakami, and Jack C. H. Lin. Theory of one-tape linear-time turing machines. Theor. Comput. Sci., 411(1):22-43, 2010. URL: https://doi.org/10.1016/j.tcs.2009.08.031.