×

Comparing complexity classes. (English) Zbl 0331.02020


MSC:

03D10 Turing machines and related notions
03D99 Computability and recursion theory
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Book, R., On languages accepted in polynomial time, SIAM J. computing, 1, 281-287, (1972) · Zbl 0251.68042
[2] Book, R.; Greibach, S., Quasirealtime languages, Math. systems theory, 4, 97-111, (1970) · Zbl 0188.33102
[3] Book, R.; Greibach, S.; Wegbreit, B., Time-and tape-bounded Turing acceptors and afls, J. computer system sci., 4, 606-621, (1970) · Zbl 0206.28702
[4] Book, R.; Greibach, S.; Ibarra, O.; Wegbreit, B., Tape-bounded Turing acceptors and principal afls, J. computer system sci., 4, 622-625, (1970) · Zbl 0206.28703
[5] Book, R.; Wegbreit, B., A note on AFLS and bounded erasing, Information and control, 19, 18-29, (1971) · Zbl 0237.68021
[6] Borodin, A., Computational complexity—theory and practice, (), 35-89
[7] Cobham, A., The intrinsic computational difficulty of functions, (), 24-30
[8] Cook, S., Characterizations of pushdown machines in terms of time-bounded computers, J. assoc. comput. Mach., 18, 4-18, (1971) · Zbl 0222.02035
[9] Cook, S., The complexity of theorem-proving procedures, (), 151-158
[10] Cook, S., A hierarchy for nondeterministic time complexity, J. computer system sci., 7, 343-353, (1973) · Zbl 0278.68042
[11] Fagin, R., Contributions to the model theory of finite structures, ()
[12] Ginsburg, S.; Greibach, S., Principal AFL, J. computer system sci., 4, 308-338, (1970) · Zbl 0198.03102
[13] Hartmanis, J.; Hunt, H., The LBA problem and its importance in the theory of computing, Cornell university technical report, (1973) · Zbl 0352.68100
[14] Hartmanis, J.; Stearns, R., On the computational complexity of algorithms, Trans. amer. math. soc., 117, 285-306, (1965) · Zbl 0131.15404
[15] Ibarra, O., A note concerning nondeterministic tape complexities, J. assoc. comput. Mach, 19, 608-612, (1972) · Zbl 0245.94044
[16] Jones, J.; Selman, A., Turing machines and the spectra of first-order formulas with equality, (), 157-167
[17] Karp, R., Reducibilities among combinatorial problems, (), 85-104
[18] Meyer, A.; Stockmeyer, L., The equivalence problem for regular expression with squaring requires exponential space, (), 125-129
[19] Rogers, H., ()
[20] Ruby, S.; Fischer, P.C., Translational methods and computational complexity, (), 173-178
[21] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[22] Seiferas, J.; Fischer, M.; Meyer, A., Refinements of the nondeterministic time and space hierarchies, (), 130-137
[23] Stearns, R.; Hartmanis, J.; Lewis, P., Hierarchies of memory limited computations, (), 179-190 · Zbl 0229.02033
[24] Wegbreit, B., A generator of context-sensitive languages, J. comput. system sci., 4, 456-461, (1969) · Zbl 0205.31302
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.