Publication
STOC 1976
Conference paper

Real-time algorithms for string-matching & palindrome recognition

View publication

Abstract

We give a sufficient condition when an on-line algorithm can be transformed into a realtime 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.

Date

Publication

STOC 1976

Authors

Share