Nondeterminism and the size of two way finite automata. (English) Zbl 1282.68160
Proceedings of the 10th annual ACM symposium on theory of computing, STOC’78, San Diego, CA, USA, May 1–3, 1978. New York, NY: Association for Computing Machinery (ACM). 275-286 (1978).
For the entire collection see [Zbl 1284.68002].
MSC:
| 68Q45 | Formal languages and automata |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Cook, S. A., The complexity of theorem proving procedures, Third Annual ACM Symposium on Theory of Computing,A May 1971, 151-158. 10.1145/800157.805047 · Zbl 0253.68020 |
| [2] | Karp, R. M., Reducibility among combinatorial problems, in, “Complexity of Computer Computations”, R. E. Miller and J. W. Thatcher, eds., Plenum Press, N. Y. (1972), 85-104. |
| [3] | Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci. 4 (1970), 177-192. · Zbl 0188.33502 |
| [4] | Cook, S. and R. Sethi, Storage Requirements for Deterministic polynomial time recognizeable languages, Sixth Annual ACM Symposium on Theory of Computing, May 1974, 33-39. 10.1145/800119.803882 · Zbl 0412.68078 |
| [5] | Jones, N. D. and W. T. Laaser, Complete problems for deterministic polynomial time, Sixth Annual ACM Symposium on Theory of Computing, May 1974, 40-46. 10.1145/800119.803883 · Zbl 0376.68040 |
| [6] | Even, S. and R. E. Tarjan, A combinatorial problem which is complete in polynomial space, Seventh Annual ACM Symposium on Theory of Computing, May 1975, 66-71. 10.1145/800116.803754 |
| [7] | Schaeffer, T. J., Complexity of decision problems based on finite two-person perfect-information games, Eighth Annual ACM Symposium on Theory of Computing, May 1976, 41-49. 10.1145/800113.803629 · Zbl 0378.68033 |
| [8] | Meyer, A. R. and M. J. Fischer, Economy of description by automata, grammers, and formal systems, Twelfth Annual Symposium an Switching and Automata Theory, October 1971, 188-191. |
| [9] | Seiferas, J., unpublished manuscript, (1973). |
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.
