×

zbMATH — the first resource for mathematics

Remarks on the complexity of nondeterministic counter languages. (English) Zbl 0332.68039

MSC:
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., Time and tape complexity of pushdown automaton languages, Information and control, 13, 186-206, (1968) · Zbl 0257.68065
[2] Book, R.V., On languages accepted in polynomial time, SIAM J. comput., 1, 281-287, (1972) · Zbl 0235.68027
[3] Book, R.V., Comparing complexity classes, J. comput. system sci., 9, 213-229, (1974) · Zbl 0331.02020
[4] Book, R.V., Translational lemmas, polynomial time and (log n)J-space, Theoret. comput. sci., 1, 215-226, (1976) · Zbl 0326.68030
[5] Book, R.V.; Greibach, S.; Ibarra, O.; Wegbreit, B., Tape-bounded Turing acceptors and principal afls, J. comput. system sci., 4, 622-625, (1970) · Zbl 0206.28703
[6] Book, R.V.; Wegbreit, B., A note on AFLs and bounded erasing, Information and control, 19, 18-29, (1971) · Zbl 0237.68021
[7] Cook, S.A., Characterizations of pushdown machines in terms of time-bounded computers, J. ACM, 18, 4-18, (1971) · Zbl 0222.02035
[8] Davis, M., Computability and unsolvability, (1958), McGraw-Hill New York · Zbl 0080.00902
[9] Fischer, P.C.; Meyer, A.R.; Rosenberg, A.L., Counter machines and counter languages, Math. systems theory, 2, 265-283, (1968) · Zbl 0165.32002
[10] S.A Greibach, A note on the recognition of one-counter languages, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge, to appear.
[11] S. Greibach, Erasable context-free languages, submitted for publication. · Zbl 0317.68059
[12] Hopcroft, J.E.; Ullman, J.D., Some results on tape-bounded Turing machines, J. ACM, 3, 168-177, (1969) · Zbl 0188.33501
[13] Ibarra, O.H., On two-way multihead automata, J. comput. system sci., 7, 28-36, (1963) · Zbl 0256.68028
[14] Minsky, M., Recursive unsolvability of Post’s problem of tag and other topics in the theory of Turing machines, Ann. of math., 74, 437-455, (1961) · Zbl 0105.00802
[15] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[16] Seiferas, J.I.; Fischer, M.J.; Meyer, A.R., Refinements of the nondeterministic time and space hierarchies, Proc. 14th annual symposium on switching and automata theory, 130-137, (October 1973), Iowa City, Iowa
[17] Wegbreit, B., A generator of context-sensitive languages, J. comput. system sci., 3, 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.