One Pebble Versus ϵ · log n Bits
Pages 55 - 69
Abstract
We show that, for any ϵ > 0, there exists a language accepted in strong ϵ log n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages.
References
[1]
Alberts, M.: Space complexity of alternating Turing machines, Proc. Int. Conf. Fundamentals of Computation Theory (L. Budach, Ed.), LNCS 199, Springer-Verlag, Berlin 1985, 1-7.
[2]
Alt, H., Mehlhorn, K.: A language over a one symbol alphabet requiring only O(log log n) space, SIGACT news, 7, 1975, 31-33.
[3]
Bertoni, A., Mereghetti, C., Pighizzini, G.: An optimal lower bound for nonregular languages, Information Processing Letters, 50, 1994, 289-292. (Corrigendum: ibid., 52, 1994, 339).
[4]
Bertoni, A., Mereghetti, C., Pighizzini, G.: Strong optimal lower bounds for Turing machines that accept nonregular languages, Proc. 20th Int. Symp. Mathematical Foundations of Computer Science (J. Wiedermann, P. Hájek, Eds.), LNCS 969, Springer-Verlag, Berlin 1995, 309-318.
[5]
Chang, J., Ibarra, O., Palis, M., Ravikumar, B.: On pebble automata, Theoretical Computer Science, 44, 1986, 111-121.
[6]
Freedman, A., Ladner, R.: Space bounds for processing contentless inputs, Journal of Computer and System Sciences, 11, 1975, 118-128.
[7]
Geffert, V.: Nondeterministic computations in sublogarithmic space and space constructibility, SIAM Journal on Computing, 20, 1991, 484-498.
[8]
Geffert, V.: Tally version of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space, SIAM Journal on Computing, 22, 1993, 102-113.
[9]
Geffert, V.: A Variant of inductive counting, Theoretical Computer Science, 237, 2000, 465-475.
[10]
Geffert, V., Mereghetti, C., Pighizzini, G.: Sublogarithmic bounds on space and reversals, SIAM Journal on Computing, 28, 1999, 325-340.
[11]
Geffert, V., Pardubská, D.: Factoring and testing primes in small space, Proc. 35th SOFSEM -- Theory and Practice of Computer Science (M. Nielsen, A. Ku¿era, P. Bro Miltersen, C. Palamidessi, P. T¿ma, F. Valencia, Eds.), LNCS 5404, Springer-Verlag, Berlin 2009, 291-302.
[12]
Hennie, F.: One-tape, off-line Turing machine computations, Information and Control, 8, 1965, 553-578.
[13]
Hopcroft, J., Ullman, J.: Some results on tape-bounded Turing machines, Journal of the ACM, 16, 1969, 168-177.
[14]
Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation, Addison-Wesley, Reading MA, 1979.
[15]
Hromkovi¿, J., Rovan, B., Slobodová, A.: Deterministic versus nondeterministic space in terms of synchronized alternating machines, Theoretical Computer Science, 132, 1994, 319-336.
[16]
Inoue, A., Ito, A., Inoue, K., Okazaki, T.: Some properties of one-pebble Turing machines with sublogarithmic space, Theoretical Computer Science, 341, 2005, 138-149.
[17]
Iwama, K.: ASPACE(o(log log n)) is regular, SIAM Journal on Computing, 22, 1993, 136-146.
[18]
Lewis, P., Stearns, R., Hartmanis, J.: Memory bounds for the recognition of context free and context sensitive languages, Conf. Record 6th IEEE Symp. Switching Circuit Theory and Logical Design, 1965, 191-202.
[19]
Mereghetti, C.: Testing the descriptional power of small Turing machines on nonregular language acceptance, International Journal of Foundations of Computer Science, 19, 2008, 827-843.
[20]
Savitch, W.: Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences, 4, 1970, 177-192.
[21]
Stearns, R., Hartmanis, J., Lewis, P.: Hierarchies of memory limited computations, Conf. Record 6th IEEE Symp. Switching Circuit Theory and Logical Design, 1965, 179-190.
[22]
Sudborough, I.: Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, Proc. 21st IEEE Symp. Foundations of Computer Science, 1980, 62-73.
[23]
Szepietowski, A.: Turing machines with sublogarithmic space, LNCS 843, Springer-Verlag, Berlin, 1994.
- One Pebble Versus ϵ · log n Bits
Recommendations
Some properties of one-pebble turing machines with sublogarithmic space
This paper investigates some aspects of the accepting powers of deterministic, nondeterministic, and alternating one-pebble Turing machines with spaces between log log n and log n. We first investigate a relationship between the accepting powers of two-...
A note on alternating one-pebble Turing machines with sublogarithmic space
Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w@?{a,b}^+} is not accepted by any alternating one-...
Inkdot versus Pebble over Two-Dimensional Languages
This paper investigates a relationship between inkdot and one-pebble for two-dimensional finite automata (2-fa's). Especially we show that (1) alternating inkdot 2-fa's are more powerful than nondeterministic one-pebble 2-fa's, and (2) there is a set ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IOS Press
Netherlands
Publication History
Published: 01 January 2010
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in