Abstract
The complexity of predicates on several classes of formal languages is studied. For finite automata, pushdown automata, and several classes of stack automata, every nontrivial predicate on the languages accepted by the 1-way devices requires as much time and space as the recognition problem for any language accepted by the corresponding 2-way devices. Moreover there are nontrivial predicates
on the languages accepted by the 1-way devices such that
is the accepted language of some corresponding one or two head 2-way device. Thus our lower bounds are fairly tight.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. A. Cook, The complexity of theorem-proving procedures.Proc. 3rd Annual ACM Symp. on Theory of Computing, May, 1971.
R. M. Karp, Reducibility among combinatorial problems, inComplexity of Computer Computations, (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York, 1972.
A. R. Meyer, Weak monadic second order of successor is not elementary recursive-preliminary report (unpublished).
M. J. Fischer andM. O. Rabin, Super-exponential complexity of Presburger arithmetic,SIAM-AMS Proc., vol. 7, Amer. Math. Soc., Providence, R.I., 1974.
L. J. Stockmeyer andA. R. Meyer, World problems requiring exponential time: preliminary report,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.
H. B. Hunt, III andD. J. Rosenkrantz, Computational parallels between the regular and context-free languages,Proc. 6th Annual ACM Symposium on Theory of Computing, May, 1974.
H. B. Hunt, III,D. J. Rosenkrantz, andT. G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages (submitted for publication).
W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities,J. Comput. System Sci. 4 (1970), 177–192.
J. Hartmanis andH. B. Hunt, III, The lba problem and its importance in the theory of computing,SIAM-AMS Proc., vol. 7, Amer. Math. Soc. Providence, R.I., 1974.
N. Jones, Preliminary report: reducibility among combinatorial problems in logn space.Proc. 7th Annual Princeton Conference on Information Sciences and Systems, March, 1973.
I. H. Sudborough, On tape-bounded complexity classes and multi-head finite automata,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.
N. D. Jones andW. T. Laaser, Complete problems for deterministic polynomial time,Proc. 6th Annual ACM Symp. on Theory of Computing, May, 1974.
S. A. Cook, An observation on time-storage tradeoff,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.
S. A. Cook andR. Sethi, Storage requirements for deterministic polynomial time recognizable languages,Proc. 6th Annual ACM Symp. on Theory of Computing, May, 1974.
A. V. Aho, Nested stack automata,J. Assoc. Comput. Mach. 16 (1969), 383–406.
J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969.
A. V. Aho, Indexed grammars—an extension of context-free grammars,J. Assoc. Comput. Mach. 15 (1968), 647–671.
M. J. Fischer, “Grammars with Macro-like Productions,” Ph.D. Dissertation, Harvard University, 1968.
M. J. Fischer, Grammars with macro-like productions,Proc. 9th Annual IEEE Symp. on Switching and Automata Theory, October, 1968.
H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
W. C. Rounds, Complexity of recognition in intermediate-level languages,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.
J. E. Hopcroft andJ. D. Ullman, Nonerasing stack automata,J. Comput. System Sci. 1 (1967), 166–186.
S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers,J. Assoc. Comput. Mach. 18 (1971), 4–18.
O. H. Ibarra, 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 (1971), 88–117.
F. C. Hennie andR. E. Stearns, Two-tape simulation of multi-tape Turing macnines,J. Assoc. Comput. Mach,13 (1966), 533–546.
O. H. Ibarra, A note concerning nondeterministic tape complexities.J. Assoc. Comput. Mach. 19 (1972), 608–612.
J. I. Seiferas, M. J. Fischer, andA. R. Meyer, Refinements of the nondeterministic time and space hierarchies,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.
W. C. Rounds, Tree-oriented proofs of some theorems on context-free and indexed languages,Proc. 2nd Annual ACM Symp. on Theory of Computing, May, 1970.
W. C. Rounds, Mappings and grammars on trees,Math. Systems Theory 4 (1970), 257–287.
V. Rajlich, Absolutely parallel grammars and two-way deterministic finite-state transducers,Proc. 3rd Annual ACM Symp. on Theory of Computing, May 1971.
S. A. Greibach, The hardest context-free language,SIAM J. Comput. 2 (1973), 304–310.
H. B. Hunt, III, On the time and tape complexity of languages I,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.
H. B. Hunt, III, “On the Time and Tape Complexity of Languages,” Ph.D. Dissertation, Cornell University, 1973.
R. Book, On languages accepted in polynomial time,SIAM J. Comput. 1 (1972).
Z. Galil, Two-way deterministic pushdown automaton languages and some open problems in the theory of computation,Proc. 15th Annual IEEE Symp. on Switching and Automata Theory, October, 1974.
D. J. Rosenkrantz, Programmed grammars and classes of formal languages,J. Assoc. Comput. Mach. 16 (1969), 107–131.
S. A. Greibach andJ. E. Hopcroft, Scattered context grammars,J. Comput. System Sci. 3 (1969), 233–247.
A. V. Aho, J. E. Hopcroft, andJ. D. Ullman, Time and tape complexity of pushdown automaton languages,Information and Control 13 (1968), 186–206.
H. B. Hunt, III, “On the Complexity of Finite, Pushdown, and Stack Automata,” MRC Technical Summary Report No. 1504, Mathematics Research Center, University of Wisconsin-Madison, 1975.
Author information
Authors and Affiliations
Additional information
This research was sponsored in part by an NSF graduate fellowship in computer science at Cornell University, NSF grant GJ-35570 at Princeton University, and by United States Army Contract No. DA-31-124-ARO-D-462 at the University of Wisconsin.
Rights and permissions
About this article
Cite this article
Hunt, H.B. On the complexity of finite, pushdown, and stack automata. Math. Systems Theory 10, 33–52 (1976). https://doi.org/10.1007/BF01683261
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01683261