Abstract
A theory for the derivation of on-line algorithms is presented. The algorithms are derived in the Bird-Meertens calculus for program transformations. This calculus provides a concise functional notation for algorithms, and a few powerful theorems for proving equalities of functions. The theory for the derivation of on-line algorithms is illustrated with the derivation of an algorithm for finding palindromes.
An on-line linear-time random access machine (RAM) algorithm for finding the longest palindromic substring in a string is derived. For the purpose of finding the longest palindromic substring, all maximal palindromic substrings are computed. The list of maximal palindromes obtained in the computation of the longest palindrome can be used for other purposes such as finding the largest palindromic rectangle in a matrix and finding the shortest partition of a string into palindromes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Apostolico and Z. Galil, editors.Combinatorial Algorithms on Words, NATO ASI Series F, volume 12. Springer-Verlag, Berlin, 1985.
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.
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.
R. S. Bird, J. Gibbons, and G. Jones. Formal derivation of a pattern matching algorithm.Science of Computer Programming, 12:93–104, 1989.
R. S. Bird and P. Wadler.Introduction to Functional Programming. Prentice-Hall, Englewood Cliffs, NJ, 1988.
S. N. Cole. Real-time computation byn-dimensional iterative arrays of finite-state machines.IEEE Transactions on Computers, 18(4):349–365, 1969.
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.
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.
M. M. Fokkinga. Law and Order in Algorithmics. Ph.D. thesis, Twente University, 1992.
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.
Z. Galil. Two fast simulations which imply some fast string matching and palindrome-recognition algorithms.Information Processing Letters, 4:85–87, 1976.
Z. Galil. Palindrome recognition in real time by a multitape Turing machine.Journal of Computers and Systems Sciences, 16:140–157, 1978.
Z. Galil. String matching in real time.Journal of the ACM, 28(1): 134–149, 1981.
Z. Galil and J. Seiferas. A linear-time on-line recognition algorithm for “Palstar.”Journal of the ACM, 25(1): 102–111, 1978.
J. A. Goguen. Memories of ADJ.Bulletin of the EATCS, 39:97–102, 1989.
J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979.
J. Jeuring. Finding palindromes. InProceedings SION Computing Science in the Netherlands, pages 123–140, 1988.
J. Jeuring. Algorithms from theorems. In M. Broy and C. B. Jones, editors,Programming Concepts and Methods, pages 247–266. North-Holland, Amsterdam, 1990.
J. Jeuring. The derivation of hierarchies of algorithms on matrices. In B. Möller, editor,Constructing Programs from Specifications, pages 9–32. North-Holland, Amsterdam, 1991.
D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings.SIAM Journal on Computing, 6:323–350, 1978.
G. Malcolm. Data structures and program transformation.Science of Computer Programming, 14:255–279, 1990.
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.
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.
L. Meertens. Paramorphisms. Technical Report CS-R9005, CWI, 1990. To appear inFormal Aspects of Computing.
O. de Moor. List partitions. To appear inFormal Aspects of Computing.
J. I. Seiferas. Iterative arrays with direct central control.Acta Informatica, 8:177–192, 1977.
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.
P. Weiner. Linear pattern matching algorithms. InIEEE Symposium on Switching and Automata Theory, volume 14, pages 1–11, 1973.
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.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
This research was supported by the Dutch organization for scientific research NWO, under NFI project STOP, project number NF 62/63-518.
Rights and permissions
About this article
Cite this article
Jeuring, J. The derivation of on-line algorithms, with an application to finding palindromes. Algorithmica 11, 146–184 (1994). https://doi.org/10.1007/BF01182773
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01182773