×

Iterated stack automata and complexity classes. (English) Zbl 0758.68029

Inf. Comput. 95, No. 1, 21-75 (1991); corrigendum ibid. 267, 164-167 (2019).
Iterated stacks and iterated pushdowns are defined from the respective elementary storage types of a repeated application of a “stack of \(X\)” resp. “pushdown of \(X\)” construction on a storage type \(X\).
The increase in computational power of automata using such storage types in the investigated cases is exponential for “pushdown of” resp. doubly exponential for “stack of”.
A typical result shown in the article is the characterization of the class \(\text{DTIME}(\exp_ k(\text{poly}))\) by \((k+1)\)-iterated multi- head pushdown automata. Here \(\exp_ k(\text{poly})\) means 2 to the 2 to the …to the 2 to the \(p\) (\(k\) iterations of “2 to the”) for some polynomial \(p\).
Similar results hold for iterated versions of stack automata, nested stack automata, checking stack automata, and stack-pushdown automata.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V., Indexed grammars, an extension of context-free grammars, J. Assoc. Comput. Mach., 15, 647-671 (1968) · Zbl 0175.27801
[2] Aho, A. V., Nested stack automata, J. Assoc. Comput. Mach., 16, 383-406 (1969) · Zbl 0184.28603
[3] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Ma) · Zbl 0326.68005
[4] Asveld, P. R.J., Controlled iteration grammars and full hyper-AFL’s, Inform. and Control, 34, 248-269 (1977) · Zbl 0363.68099
[5] Asveld, P. R.J.; van Leeuwen, J., (Infinite Chains of Hyper-AFL’s (1975), Iwente University of Technology), Memorandum 99
[6] Beeri, C., Two-way nested stack automata are equivalent to two-way stack automata, (J. Comput. System Sci., 10 (1975)), 317-339 · Zbl 0331.68029
[7] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[8] Cook, S. A., Characterizations of pushdown machines in terms of time-bounded computers, J. Assoc. Comput. Mach., 18, 4-18 (1971) · Zbl 0222.02035
[9] Damm, W., The IO- and OI-hierarchies, Theoret. Comput. Sci., 20, 95-206 (1982) · Zbl 0478.68012
[10] Damm, W.; Goerdt, A., An automata-theoretical characterization of the OI-hierarchy, Inform. and Control, 71, 1-32 (1986) · Zbl 0628.68061
[11] Engelfriet, J., Three hierarchies of transducers, Math. Systems Theory, 15, 95-125 (1982) · Zbl 0509.68078
[12] Engelfriet, J., Iterated pushdown automata and complexity classes, (Proceedings, 15th STOC. Proceedings, 15th STOC, Boston (1983)), 365-373
[13] Engelfriet, J., (Context-Free Grammars with Storage (1986), Leiden University), Report 86-11
[14] Engelfriet, J.; Hoogeboom, H. J., (Proceedings 16th ICALP, Lecture Notes in Computer Science, Vol. 372 (1989), Springer-Verlag: Springer-Verlag Berlin), 289-303
[15] Engelfriet, J.; Rozenberg, G.; Slutzki, G., Tree transducers, \(L\) systems, and two-way machines, J. Comput. System Sci., 20, 150-202 (1980) · Zbl 0426.68075
[16] Engelfriet, J.; Schmidt, E. M., IO and OI, II, J. Comput. System Sci., 16, 67-99 (1977/1978) · Zbl 0371.68020
[17] Engelfriet, J.; Schmidt, E. M.; van Leeuwen, J., Stack machines and classes of nonnested macro languages, J. Assoc. Comput. Mach., 27, 96-117 (1980) · Zbl 0428.68087
[18] Engelfriet, J.; Slutzki, G., Extended macro grammars and stack controlled machines, J. Comput. System Sci., 29, 366-408 (1984) · Zbl 0575.68081
[19] Engelfriet, J.; Vogler, H., Pushdown machines for the macro tree transducer, Theoret. Comput. Sci., 42, 251-368 (1986) · Zbl 0619.68065
[20] Engelfriet, J.; Vogler, H., Look-ahead on pushdowns, Inform. and Comput., 73, 245-279 (1987) · Zbl 0625.68063
[21] Engelfriet, J.; Vogler, H., High level tree transducers and iterated pushdown tree transducers, Acta Inform., 26, 131-192 (1988) · Zbl 0633.68073
[22] Fischer, M. J., Two characterizations of the context-sensitive languages, (IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory (1969)), 149-165
[23] Galil, Z., Hierarchies of complete problems, Acta Inform., 6, 77-88 (1977) · Zbl 0304.68044
[24] Ginsburg, S., (Algebraic and Automata-Theoretic Properties of Formal Languages (1975), North-Holland: North-Holland Amsterdam) · Zbl 0325.68002
[25] Ginsburg, S.; Greibach, S. A.; Harrison, M. A., Stack automata and compiling, J. Assoc. Comput. Mach., 14, 389-418 (1967) · Zbl 0171.14803
[26] Goldstine, J., Automata with data storage, (Proceedings of a Conference on Theoretical Computer Science. Proceedings of a Conference on Theoretical Computer Science, Waterloo (1977)), 239-246
[27] Greibach, S. A., Checking automata and one-way stack languages, J. Comput. System Sci., 3, 196-217 (1969) · Zbl 0174.02702
[28] Greibach, S. A., Full AFLs and nested iterated substitution, Inform. and Control, 16, 7-35 (1970) · Zbl 0188.03102
[29] Greibach, S. A., Visits, crosses, and reversals for nondeterministic off-line machines, Inform. and Control, 36, 174-216 (1978) · Zbl 0375.02027
[30] Greibach, S. A., One-way finite visit automata, Theoret. Comput. Sci., 6, 175-221 (1978) · Zbl 0368.68059
[31] Greibach, S. A., Hierarchy theorems for two-way finite state transducers, Acta Inform., 11, 89-101 (1978) · Zbl 0398.68038
[32] Hoare, C. A.R., Proof of correctness of data representations, Acta Inform., 1, 271-281 (1972) · Zbl 0244.68009
[33] Hopcroft, J. E.; Ullman, J. D., An approach to a unified theory of automata, Bell System Tech. J., 46, 1793-1829 (1967) · Zbl 0155.34303
[34] Hopcroft, J. E.; Ullman, J. D., Nonerasing stack automata, J. Comput. System Sci., 1, 166-186 (1967) · Zbl 0166.00506
[35] Hopcroft, J. E.; Ullman, J. D., (Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0426.68001
[36] Hunt, H. B., On the complexity of finite, pushdown, and stack automata, Math. Systems Theory, 10, 33-52 (1976) · Zbl 0351.68016
[37] Ibarra, O. H., Characterizations of some tape and time complexity classes of Turing machines in terms of multi-head and auxiliary stack automata, J. Comput. System Sci., 5, 88-117 (1971) · Zbl 0255.68012
[38] Jones, N. D., Space-bounded reducibility among combinatorial problems, J. Comput. System Sci., 11, 68-85 (1975) · Zbl 0317.02039
[39] Jones, N. D.; Laaser, W. T., Complete problems for deterministic polynomial time, Theoret. Comput. Sci., 3, 105-117 (1977) · Zbl 0352.68068
[40] Kiel, D. I., Two-way a-transducers and AFL, J. Comput. System Sci., 10, 88-109 (1975) · Zbl 0303.68048
[41] Kowalczyk, W.; Niwinski, D.; Tiuryn, J., A generalization of Cook’s auxiliarypushdown-automata theorem, Fund. Inform., 12, 497-506 (1989) · Zbl 0691.68042
[42] Ladner, R. E.; Lipton, R. J.; Stockmeyer, L. J., Alternating pushdown and stack automata, SIAM J. Comput., 13, 135-155 (1984) · Zbl 0538.68039
[43] Maibaum, T. S.E., A generalized approach to formal languages, J. Comput. System Sci., 8, 409-439 (1974) · Zbl 0361.68113
[44] Maslov, A. N., The hierarchy of indexed languages of an arbitrary level, Soviet Math. Dokl., 15, 1170-1174 (1974) · Zbl 0316.68042
[45] Maslov, A. N., Multi-level stack automata, Problems Inform. Transmission, 12, 38-43 (1976)
[46] Parchmann, R.; Duske, J.; Specht, J., On deterministic indexed languages, Inform. and Control, 45, 48-67 (1980) · Zbl 0438.68035
[47] Rajlich, V., Absolutely parallel grammars and two-way finite state transducers, J. Comput. System Sci., 6, 324-342 (1972) · Zbl 0246.68013
[48] Rozenberg, G.; Salomaa, A., (The Mathematical Theory of \(L\) Systems (1980), Academic Press: Academic Press New York) · Zbl 0365.68072
[49] Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 218-235 (1980) · Zbl 0445.68034
[50] Scott, D., Some definitional suggestions for automata theory, J. Comput. System Sci., 1, 187-212 (1967) · Zbl 0164.32103
[51] van Leeuwen, J., Variations of a new machine model, (Proceedings, 17th FOCS (1976))
[52] Vogel, J.; Wagner, K., Two-way automata with more than one storage medium, Theoret. Comput. Sci., 39, 267-280 (1985) · Zbl 0604.68055
[53] Vogler, H., Iterated linear control and iterated one-turn pushdowns, Math. Syst. Theory, 19, 117-133 (1986) · Zbl 0636.68106
[54] Vogler, H., The OI-hierarchy is closed under control, Inform. and Comput., 78, 187-204 (1988) · Zbl 0655.68103
[55] Wagner, K.; Wechsung, G., (Computational Complexity (1986), Reidel: Reidel Dordrecht)
[56] Wand, M., An algebraic formulation of the Chomsky-hierarchy, (Category Theory Applied to Computation and Control. Category Theory Applied to Computation and Control, Lecture Notes in Computer Sci., Vol. 25 (1975), Springer-Verlag: Springer-Verlag Berlin), 209-213 · Zbl 0305.68056
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.