On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition
- 1 November 1975
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 7 (4) , 26-30
- https://doi.org/10.1145/990502.990505
Abstract
We give a sufficient condition when an on-line algorithm can be transformed into a real-time algorithm. We use this condition to construct real-time algorithms for string-matching and palindrome recognition problems by random access machines and by Turing machines.Keywords
This publication has 2 references indexed in Scilit:
- A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a StringJournal of the ACM, 1975
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965