Time Bounded Random Access Machines with Parallel Processing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Time Bounded Random Access Machines with Parallel Processing

Full text

Pdf (1.23 MB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 1 (January 1979) table of contents

Pages: 103 - 118

Year of Publication: 1979

ISSN:0004-5411

Authors

Walter J. Savitch	Computer Science Program, Department of AP & IS, University of California, San Diego, La Jolla, CA and Mathematisch Centrum, Amsterdam
Michael J. Stimson	Systems Research Operation, Science Applications, Inc., La Jolla, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 30, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322108.322119 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	CHANDRA, A K, AND STOCKMEYER, L.J. AlternaUon Proc 17th Annual IEEE Symp on Foundauons of Computer Sctence, Houston, Texas, Oct 1976, pp 98-108
	3	COOK, S.A, AND RECKHOW, R A Time bounded random access machines J Comptr Syst Sc~. 7 (1973), 354--375
	4	GLUSHKOV, V M, {GNATYEV, M D, MYASNIKOV, V A, AND TORGASHEV, V A Recurswe machmes and computing technology Proc IFIP Congress on lnformauon Processing, Aug 1974, pp 66-70
	5	HARTMANIS, J Computattonal complexity of random access stored program machines Math Syst Theory 5 (1971), 232-245
	6	HARTMANIS, j, AND SIMON, J On the power of multiplication m random access machines Proc 15th Annual IEEE Symp on Sw,tchmg and Automata Theory, New Orleans, La, Oct 1974, pp 13-23
	7	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	8	KOZEN, D. On parallelism in Turmg machmes Proc 17th Annual IEEE Symp on Foundations of Computer Science, Houston, Texas, Oct 1976, pp 89-97
	9	PRATT, V R, AND STOCK_MEYER, L J. A characterization of the power of vector machines J Comptr Syst Scl 12 (1976), 198-221
	10	SAVITCH, W.J Relatlonshtps between nondetermlmStlC and determmtst~c tape complexmes J Comptr Syst Sc: 4 (1970), 177-192
	11	SAVITCH, W J Recurslve Tunng machines Intern J Comptr Math 6 (1977), 3-31
	12	SAVITCH, W.J., AND STIMSON, M J The complextty of ttme bounded recurslve computauons Proc 1976 Conf on Informauon Soences and Systems, The Johns Hopkins U, Baltimore, Md, Apnl 1976
	13	Michael Joseph Stimson, The complexity of parallel algorithms., 1976

CITED BY 5

	C. Slot , P. van Emde Boas, On tape versus core an application of space efficient perfect hash functions to the invariance of space, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.391-400, December 1984
	John H. Reif, Symmetric Complementation, Journal of the ACM (JACM), v.31 n.2, p.401-421, April 1984
	Gary Lewandowski , Anne Condon , Eric Bach, Asynchronous Analysis of Parallel Dynamic Programming Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.425-438, April 1996
	John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States
	Peter R. J. Asveld, Fuzzy context-free languages: part 2: Recognition and parsing algorithms, Theoretical Computer Science, v.347 n.1-2, p.191-213, 30 November 2005