A Linear-Time On-Line Recognition Algorithm for ``Palstar''

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Linear-Time On-Line Recognition Algorithm for ``Palstar''

Full text

Pdf (511 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 102 - 111

Year of Publication: 1978

ISSN:0004-5411

Authors

Zvi Galil	Department of Mathematical Sciences, Computer Science Division, Tel Aviv University, Tel Aviv, Israel
Joel Seiferas	Computer Science Department, 314 Whitmore Laboratory, The Pennsylvania State University, University Park, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 27, Citation Count: 1

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/322047.322056 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	AHO, A V, HOPCROFr, J E, AND ULLMAN, J D T~me and tape complexity of pushdown automaton languages Inform and Control 13, 3 (Sept 1968), 186-206
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	FIschER, M J , AND PATERSON, M S Stnng-matchlng and other products in Complexzty of Computation (SIAM-AMS Proc, Vol 7), R M Karp, Ed , Amer Math Soc, Providence, R I , 1974, pp 113-125
	4	Patrick C. Fischer , Albert R. Meyer , Arnold L. Rosenberg, Real-Time Simulation of Multihead Tape Units, Journal of the ACM (JACM), v.19 n.4, p.590-607, Oct. 1972 [doi>10.1145/321724.321726]
	5	G'ALIL, Z Pahndrome recognition m real time by a multttape Turmg machine To appear m J Comptr Syst Scz
	6	KNUTn, D E , MORRIS, J H JR, ANt) PRAY, V R Fast pattern matchmg in strings. SIAM J Comptng. 6, 2 (June 1977), 323-350
	7	KNtJTH, D E, AND PRAa-r, V R Automata theory can be useful Rough draft only, Comptr Scl Dept , Stanford U , Stanford, Cahf, Dec 1971
	8	Glenn Manacher, A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String, Journal of the ACM (JACM), v.22 n.3, p.346-351, July 1975 [doi>10.1145/321892.321896]
	9	SEIFERAS, j \| , AND GALIL, Z Real-time recognmon of substrmg repetition and reversal. To appear m Math Syst Theory
	10	SUSENKO, A O Recognmon of pahndromes by multlhead Tunng machines (m Russian) In Problems ~n the Constructtve Trend tn Mathemattcs, VI (Proc Steklov Inst Math., No. 129), V.P Orevkov and N A ~amn, Eds, Acad Scl USSR, 1973, pp 30-202, Enghsh transl, by R.H. Sflverman, Amer. Math Soc, Providence, R I , 1976, pp 25-208
	11	SHSENrO, A O A s~mphfled proof of real-time recogmzabdlty of pahndromes on Turing machines (m Russian) In Theoreucal Apphcattons of Methods of Mathematical Logic, II (Proc. Scientific Seminars of the Leningrad Branch of the Steklov Inst of Math , Vol 68) G E Mmtz and V P Orevkov, Eds , Acad So USSR, 1977, pp 123-139
	12	I. H. Sudborough, On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, Proceedings of the eighth annual ACM symposium on Theory of computing, p.141-148, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803642]