×
Sudborough, I. H.

On tape-bounded complexity classes and multihead finite automata. (English) Zbl 0299.68031

J. Comput. Syst. Sci. 10, 62-76 (1975).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0299.68031

Cited in 34 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDF BibTeX XML Cite
\textit{I. H. Sudborough}, J. Comput. Syst. Sci. 10, 62--76 (1975; Zbl 0299.68031)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Harrison, M.A.; Ibarra, O.H., Multitape and multihead pushdown automata, Information and control, 13, 433-470, (1968) · Zbl 0174.02701
[2] Hartmanis, J., On nondeterminancy in simple computing devices, Acta informatica, 1, 336-344, (1972) · Zbl 0229.68014
[3] Hopcroft, J.E.; Ullman, J.D., ()
[4] Ibarra, O.H., One two-way multihead automata, J. comput. system sci., 7, 28-36, (1973) · Zbl 0256.68028
[5] Jones, N.D., Preliminary report: reducibility among combinatorial problems in log n space, (), 547-551
[6] Lewis, P.M.; Stearns, R.E.; Hartmanis, J., Memory bounds for the recognition of context-free and context-sensitive languages, (), 199-212 · Zbl 0272.68054
[7] Meyer, A.R.; Stockmeyer, L.J., Word problems requiring exponential time, () · Zbl 0359.68050
[8] Rosenberg, A.L., On multihead finite automata, IBM J. res develop., 10, 388-394, (1966) · Zbl 0168.01303
[9] Savitch, W.J., Multihead automata and context-sensitive languages, () · Zbl 0255.68021
[10] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[11] {\scI. H. Sudborough}: One-way multihead writing finite automata, unpublished. · Zbl 0337.02023
[12] Sudborough, I.H., Bounded-reversal multihead finite automata languages, Information and control, 25, 317-328, (1974) · Zbl 0282.68033
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.