Simon, Janos On tape-bounded probabilistic Turing machine acceptors. (English) Zbl 0473.68044 Theor. Comput. Sci. 16, 75-91 (1981). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 9 Documents MSC: 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q25 Analysis of algorithms and problem complexity Keywords:deterministic and probabilistic tape complexities × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. Comput., 5, 4, 618-623 (1976) · Zbl 0353.68063 [2] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 4, 675-695 (1977) · Zbl 0366.02024 [3] Hartmanis, J.; Simon, J., On the power of multiplication in random access machines, Proc. 15th SWAT, 12-23 (1974) [4] Hartmanis, J.; Simon, J., On the structure of feasible computations, (Advances in Computers, 14 (1976), Academic Press: Academic Press New York), 1-43 · Zbl 0341.68031 [5] Hopcroft, J.; Ullman, J., Formal Languages and their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 [6] De Leeuw, K.; Moore, E. F.; Shannon, C. E.; Shapiro, N., Computability by probabilistic machines, (Automata Studies. Automata Studies, Annals of Mathematics Studies, 34 (1956), Princeton University Press: Princeton University Press Princeton, NJ), 182-212 [7] Pratt, V. R.; Stockmeyer, L. J., A characterization of the power of vector machines, Proc. 6th STOC, 122-134 (1974) · Zbl 0381.68039 [8] Pratt, V. R.; Stockmeyer, L. J., A characterization of the power of vector machines, J. Comput. System Sci., 12, 2, 198-221 (1976) · Zbl 0342.68033 [9] Santos, E. S., Probabilistic Turing machines and computability, Proc. Amer. Math. Soc., 22, 704-710 (1969) · Zbl 0186.01202 [10] Savitch, W. J., Relationship between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 2, 177-192 (1967) · Zbl 0188.33502 [11] Simon, J., On some central problems in computational complexity, (TR 75-224 (1974), Cornell University) [12] Simon, J., On feasible numbers, Proc. 9th STOC, 195-207 (1977) [13] Simon, J., On the difference between one and many, (Salomaa, A.; Steinby, M., Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, 52 (1977), Springer: Springer Berlin), 480-491 · Zbl 0364.68066 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.