Minimal Size of Counters for (Real-Time) Multicounter Automata

• Autorzy: Geffert Viliam , Bednárová Zuzana

Identyfikatory

DOI

10.3233/FI-2021-2053

• Języki publikacji: EN

Abstrakty

EN

We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)^ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small — but fixed-constant; the “space” refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is n^ɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here.

Słowa kluczowe

EN

space complexity; pushdown automata; counter automata; real-time automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 2-3
• Strony: 99--127
• Opis fizyczny: Bibliogr. 20 poz., tab., wykr.

Twórcy

autor

Geffert Viliam

• Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia

autor

Bednárová Zuzana

• Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia

Bibliografia

• [1] Hartmanis J, Lewis II P, Stearns R. Hierarchies of Memory Limited Computations. In: IEEE Conference Record on Switching Circuit Theory and Logical Design. 1965 pp. 179-190. doi:10.1109/FOCS.1965.11.
• [2] Geffert V. Space Hierarchy Theorem Revised. Theoretical Computer Science, 2003. 295(1-3):171-187. URL https://doi.org/10.1016/S0304-3975(02)00402-4.
• [3] Geffert V, Mereghetti C, Pighizzini G. Sublogarithmic Bounds on Space and Reversals. SIAM Journal on Computing, 1999. 28:325-340. doi:10.1137/S0097539796301306.
• [4] Mereghetti C. Testing the Descriptional Power of Small Turing Machines on Nonregular Language Acceptance. International Journal of Foundations of Computer Science, 2008. 19(4):827-843. URL https://doi.org/10.1142/S012905410800598X.
• [5] Szepietowski A. Turing Machines with Sublogarithmic Space, volume 843 of Lecture Notes in Computer Science Springer-Verlag, 1994. ISBN:978-0-387-58355-6.
• [6] Hopcroft J, Ullman J. Some Results on Tape-Bounded Turing Machines. Journal of the ACM, 1969. 16:168-177. URL https://doi.org/10.1145/321495.321508.
• [7] Alberts M. Space Complexity of Alternating Turing Machines. In: Proceedings of Fundamentals of Computation Theory (FCT), volume 199 of Lecture Notes in Computer Science Springer-Verlag, 1985 pp. 1-7. doi:10.1007/BFb0028785.
• [8] Iwama K. ASPACE(o(log log n)) Is Regular. SIAM Journal on Computing, 1993. 22:136-146.
• [9] Hopcroft J, Motwani R, Ullman J. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001. ASIN:B004XXS33Q.
• [10] Bednárová Z, Geffert V, Reinhardt K, Yakaryılmaz A. New Results on the Minimum Amount of Useful Space. International Journal of Foundations of Computer Science, 2016. 27:259-281. URL https://doi.org/10.1142/S0129054116400098.
• [11] Bertoni A, Mereghetti C, Pighizzini G. Strong Optimal Lower Bounds for Turing Machines That Accept Nonregular Languages. In: Proceedings of Mathematical Foundations of Computer Science (MFCS), volume 969 of Lecture Notes in Computer Science Springer-Verlag, 1995 pp. 309-318. doi:10.1007/3-540-60246-1_137.
• [12] Alt H, Mehlhorn K. A Language over a One Symbol Alphabet Requiring Only O(log log n) space. SIGACT News, 1975. 7:31-33. doi:10.1145/990502.990506.
• [13] Geffert V. Unary Coded PSPACE-Complete Languages in ASPACE(log log n). Theory of Computing Systems, 2019. 63:688-714. URL https://doi.org/10.1007/s00224-018-9844-7.
• [14] Yakaryılmaz A, Say A. Tight Bounds for the Space Complexity of Nonregular Language Recognition by Real-Time Machines. International Journal of Foundations of Computer Science, 2013. 24:1243-1253. URL https://doi.org/10.1142/S0129054113500329.
• [15] Ginsburg S, Rice H. Two Families of Languages Related to ALGOL. Journal of the ACM, 1962. 9:350-371.
• [16] Chandra A, Kozen D, Stockmeyer L. Alternation. Journal of the ACM, 1981. 28:114-133.
• [17] Geffert V, Yakaryılmaz A. Classical Automata on Promise Problems. Discrete Mathematics and Theoretical Computer Science, 2015. 17:157-180.
• [18] Geffert V. A Hierarchy That Does Not Collapse: Alternations in Low Level Space. RAIRO — Informatique théorique et Applications, 1994. 28:465-512. ISSN:0988-3754.
• [19] Freedman A, Ladner R. Space Bounds for Processing Contentless Inputs. Journal of Computer and System Sciences, 1975. 11:118-128. URL https://doi.org/10.1016/S0022-0000(75)80052-3.
• [20] Minsky M. Computation: Finite and Infinite Machines. Prentice Hall, 1967. ISBN:10:0131655639, 13:978-0131655638.