{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:25Z","timestamp":1770994165141,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1994,2,1]],"date-time":"1994-02-01T00:00:00Z","timestamp":760060800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,2]]},"DOI":"10.1007\/bf01182773","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T18:59:51Z","timestamp":1108666791000},"page":"146-184","source":"Crossref","is-referenced-by-count":12,"title":["The derivation of on-line algorithms, with an application to finding palindromes"],"prefix":"10.1007","volume":"11","author":[{"given":"Johan","family":"Jeuring","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","series-title":"NATO ASI Series F, volume 12","volume-title":"Combinatorial Algorithms on Words","year":"1985","unstructured":"A. Apostolico and Z. Galil, editors.Combinatorial Algorithms on Words, NATO ASI Series F, volume 12. Springer-Verlag, Berlin, 1985."},{"key":"CR2","series-title":"NATO ASI Series F, volume 36","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-3-642-87374-4_1","volume-title":"Logic of Programming and Calculi of Discrete Design","author":"R. S. Bird","year":"1987","unstructured":"R. S. Bird. An introduction to the theory of lists. In M. Broy, editor,Logic of Programming and Calculi of Discrete Design, pages 5?42. NATO ASI Series F, volume 36. Springer-Verlag, Berlin, 1987."},{"key":"CR3","series-title":"NATO ASI Series F, volume 55","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/978-3-642-74884-4_5","volume-title":"Constructive Methods in Computing Science","author":"R. S. Bird","year":"1989","unstructured":"R. S. Bird. Lectures on constructive functional programming. In M. Broy, editor,Constructive Methods in Computing Science, pages 151?216. NATO ASI Series F, volume 55. Springer-Verlag, Berlin, 1989."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0167-6423(89)90036-1","volume":"12","author":"R. S. Bird","year":"1989","unstructured":"R. S. Bird, J. Gibbons, and G. Jones. Formal derivation of a pattern matching algorithm.Science of Computer Programming, 12:93?104, 1989.","journal-title":"Science of Computer Programming"},{"key":"CR5","volume-title":"Introduction to Functional Programming","author":"R. S. Bird","year":"1988","unstructured":"R. S. Bird and P. Wadler.Introduction to Functional Programming. Prentice-Hall, Englewood Cliffs, NJ, 1988."},{"issue":"4","key":"CR6","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/T-C.1969.222663","volume":"18","author":"S. N. Cole","year":"1969","unstructured":"S. N. Cole. Real-time computation byn-dimensional iterative arrays of finite-state machines.IEEE Transactions on Computers, 18(4):349?365, 1969.","journal-title":"IEEE Transactions on Computers"},{"key":"CR7","first-page":"109","volume-title":"Lecture Notes in Computer Science, Vol. 415","author":"M. Crochemore","year":"1990","unstructured":"M. Crochemore and W. Rytter. Parallel computations on strings and arrays. In C. Choffrut and T. Lengauer, editors,Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, pages 109?125. Lecture Notes in Computer Science, Vol. 415. Springer-Verlag, Berlin, 1990."},{"key":"CR8","unstructured":"P. C. Fischer and M. S. Paterson. String matching and other products. In R. M. Karp, editor,SIAM-AMS Proceedings on Complexity of Computation, volume 7, pages 113?126, 1974."},{"key":"CR9","unstructured":"M. M. Fokkinga. Law and Order in Algorithmics. Ph.D. thesis, Twente University, 1992."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Z. Galil. Real-time algorithms for string-matching and palindrome recognition. InProceedings of the Eighth Annual Symposium on Theory of Computing, pages 161?173, 1976.","DOI":"10.1145\/800113.803644"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(76)90050-8","volume":"4","author":"Z. Galil","year":"1976","unstructured":"Z. Galil. Two fast simulations which imply some fast string matching and palindrome-recognition algorithms.Information Processing Letters, 4:85?87, 1976.","journal-title":"Information Processing Letters"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0022-0000(78)90042-9","volume":"16","author":"Z. Galil","year":"1978","unstructured":"Z. Galil. Palindrome recognition in real time by a multitape Turing machine.Journal of Computers and Systems Sciences, 16:140?157, 1978.","journal-title":"Journal of Computers and Systems Sciences"},{"issue":"1","key":"CR13","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1145\/322234.322244","volume":"28","author":"Z. Galil","year":"1981","unstructured":"Z. Galil. String matching in real time.Journal of the ACM, 28(1): 134?149, 1981.","journal-title":"Journal of the ACM"},{"issue":"1","key":"CR14","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/322047.322056","volume":"25","author":"Z. Galil","year":"1978","unstructured":"Z. Galil and J. Seiferas. A linear-time on-line recognition algorithm for ?Palstar.?Journal of the ACM, 25(1): 102?111, 1978.","journal-title":"Journal of the ACM"},{"key":"CR15","first-page":"97","volume":"39","author":"J. A. Goguen","year":"1989","unstructured":"J. A. Goguen. Memories of ADJ.Bulletin of the EATCS, 39:97?102, 1989.","journal-title":"Bulletin of the EATCS"},{"key":"CR16","volume-title":"Introduction to Automata Theory, Languages, and Computation.","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979."},{"key":"CR17","unstructured":"J. Jeuring. Finding palindromes. InProceedings SION Computing Science in the Netherlands, pages 123?140, 1988."},{"key":"CR18","first-page":"247","volume-title":"Programming Concepts and Methods","author":"J. Jeuring","year":"1990","unstructured":"J. Jeuring. Algorithms from theorems. In M. Broy and C. B. Jones, editors,Programming Concepts and Methods, pages 247?266. North-Holland, Amsterdam, 1990."},{"key":"CR19","first-page":"9","volume-title":"Constructing Programs from Specifications","author":"J. Jeuring","year":"1991","unstructured":"J. Jeuring. The derivation of hierarchies of algorithms on matrices. In B. M\ufffdller, editor,Constructing Programs from Specifications, pages 9?32. North-Holland, Amsterdam, 1991."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1978","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings.SIAM Journal on Computing, 6:323?350, 1978.","journal-title":"SIAM Journal on Computing"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0167-6423(90)90023-7","volume":"14","author":"G. Malcolm","year":"1990","unstructured":"G. Malcolm. Data structures and program transformation.Science of Computer Programming, 14:255?279, 1990.","journal-title":"Science of Computer Programming"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"G. Manacher","year":"1975","unstructured":"G. Manacher. A new linear-time ?on-line? algorithm for finding the smallest initial palindrome of a string.Journal of the ACM, 22:346?351, 1975.","journal-title":"Journal of the ACM"},{"key":"CR23","first-page":"289","volume-title":"CWI Monographs, volume 1","author":"L. Meertens","year":"1986","unstructured":"L. Meertens. Algorithmics?towards programming as a mathematical activity. In J. W. de Bakker, M. Hazewinkel, and J. K. Lenstra, editors,Proceedings of the CWI Symposium on Mathematics and Computer Science, pages 289?334. CWI Monographs, volume 1. North-Holland, Amsterdam, 1986."},{"key":"CR24","unstructured":"L. Meertens. Paramorphisms. Technical Report CS-R9005, CWI, 1990. To appear inFormal Aspects of Computing."},{"key":"CR25","unstructured":"O. de Moor. List partitions. To appear inFormal Aspects of Computing."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF00289248","volume":"8","author":"J. I. Seiferas","year":"1977","unstructured":"J. I. Seiferas. Iterative arrays with direct central control.Acta Informatica, 8:177?192, 1977.","journal-title":"Acta Informatica"},{"key":"CR27","unstructured":"A. O. Slisenko. Recognizing a symmetry predicate by multihead Turing machines with input. In V. P. Orverkov and N. A. Sonin, editors,Proceedings of the Steklov Institute of Mathematics, number 129, pages 25?208, 1973."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume":"14","author":"P. Weiner","year":"1973","unstructured":"P. Weiner. Linear pattern matching algorithms. InIEEE Symposium on Switching and Automata Theory, volume 14, pages 1?11, 1973.","journal-title":"IEEE Symposium on Switching and Automata Theory"},{"key":"CR29","unstructured":"A. C. Yao. A Lower Bound to Palindrome Recognition by Probabilistic Turing Machines. Technical Report STAN-CS-77-647, Computer Science Department, Stanford University, 1977."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01182773.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01182773\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01182773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:22:34Z","timestamp":1556727754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01182773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,2]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,2]]}},"alternative-id":["BF01182773"],"URL":"https:\/\/doi.org\/10.1007\/bf01182773","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,2]]}}}