k + 1 Heads Are Better than k

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

k + 1 Heads Are Better than k

Full text

Pdf (266 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 2 (April 1978) table of contents

Pages: 337 - 340

Year of Publication: 1978

ISSN:0004-5411

Authors

Andrew C. Yao	Computer Science Department, Stanford University, Stanford, CA and Massachusetts Institute of Technology, Cambridge, Massachusetts
Ronald L. Rivest	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 53, Citation Count: 2

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/322063.322076 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	FLOYD, R W Review 14,352 (of paper by Rosenberg {5}) Comptng Rev. 9, 5 (May 1968), 280
	2	IB~,~,, O H., A~qD KIM, C E On 3-head versus 2-head fimte automata. Acta Informatzca 4 (1975), 193-200
	3	NELSON, C G One-way automata on bounded languages Tech. Rep TR14-76, Harvard Ctr for Res and Comptng, July 1976.
	4	PIATKOWSKI, T F N-head finite state machines Ph D Th., U of M~ch~gan, Ann Arbor, Mlch, 1963
	5	ROSENBER(;, A L On multi-head fimte automata IBM J Res. and Develop 10 (1966), 388-394
	6	ROSErqBERG, A L Nonwrmng extensions of fimte automata Ph D Th, Rep No. BL-39, Comput Lab , Harvard U., Cambridge, Mass, 1965
	7	SODaOROUGH, I H One-way multlhead writing fimte automata Inform. and Control 30 (1976), 1-20
	8	Ivan Hal Sudborough, Computation by multi-head writing finite automata, 1971

CITED BY 2

	Pavol Dûriš , Zvi Galil, Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.177-188, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Elena Czeizler , Eugen Czeizler, Parallel communicating Watson-Crick automata systems, Acta Cybernetica, v.17 n.4, p.685-700, January 2006