×

On pebble automata. (English) Zbl 0612.68045

Steinchen (pebbles) heißen hier sehr bildhaft reversible und kumulierbare Markierungen, die eine Turing-Maschine (TM) auf ihrem Eingabeband anbringen und aufsuchen kann. 1-Steinchen-TM können Probleme in DSPACE(loglog n) bearbeiten; laut A. R. Freedman und R. E. Ladner [J. Comput. Syst. Sci. 11, 118-128 (1975; Zbl 0307.68036)] ist diese Problemklasse für TM ohne Steinchen verschlossen. Arbeitsplatz unterhalb loglog n ist für 1 Steinchen äquivalent zu konstantem Arbeitsplatz. 2-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie Automaten mit nichtlöschbarem, aber zerstörungsfrei lesbarem Keller. 3-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie 2weg-Kellerautomaten (2DPDA’s). Wesentlicher als die Fülle von Einzelergebnissen, die sichtlich der ordnenden Hand des Morphologen (Zwicky) bedürfen, ist die breite Anwendung einer Beweistechnik, die sich der Tiefensuche über dem Baum der Konfigurationen eines deterministischen Automaten bedient [M. Sipser, Theor. Comput. Sci. 10, 335-338 (1980; Zbl 0423.68011)].
Reviewer: U.Klemm

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Time and tape complexity of pushdown automata, Inform. and Control, 13, 3, 186-206 (1968) · Zbl 0257.68065
[2] Alt, H.; Mehlhorn, K., A language over a one-symbol alphabet requiring only O(loglog \(n)\) space, SIGACT Newsletter (November-December, 1975)
[3] Freedman, A. R.; Ladner, R. E., Space bounds for processing contentless inputs, J. Comput. System Sci., 11, 118-128 (1975) · Zbl 0307.68036
[4] Greibach, S. A., An infinite hierarchy of context-free languages, J. ACM, 16, 1, 91-106 (1969) · Zbl 0182.02002
[5] Greibach, S. A., Checking automata and one-way stack languages, J. Comput. System Sci., 3, 196-217 (1969) · Zbl 0174.02702
[6] Hartmanis, J.; Berman, L., Tapebounds for processing languages over unary alphabet, Theoret. Comput. Sci., 3, 213-224 (1976) · Zbl 0351.68014
[7] Hennie, F. C., One-tape off-line Turing machine computations, Inform. and Control, 8, 6, 553-578 (1965) · Zbl 0231.02048
[8] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[9] Ibarra, O. H., Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, J. Comput. System Sci., 5, 2, 88-117 (1971) · Zbl 0255.68012
[10] Monien, B.; Sudborough, I. H., On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Theoret. Comput. Sci., 21, 237-253 (1982) · Zbl 0493.68046
[11] Ritchie, R.; Springsteel, F., Language recognition by marking automata, Inform. and Control, 20, 313-330 (1972) · Zbl 0242.68032
[12] Rosenfeld, A., Picture Languages (1979), Academic Press: Academic Press New York · Zbl 0471.68074
[13] Sipser, M., On halting space-bounded computations, Theoret. Comput. Sci., 10, 335-338 (1980) · Zbl 0423.68011
[14] Stearns, R.; Hartmanis, J.; Lewis, P. M., Hierarchies of memory limited computations, (Proc. Symp. on Switching Circuit Theory and Logical Design (1965)), 191-202 · Zbl 0229.02033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.