Recognizing certain repetitions and reversals within strings
- 1 October 1976
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 236-252
- https://doi.org/10.1109/sfcs.1976.25
Abstract
Let P1 = {w ε Σ*:w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.Keywords
This publication has 10 references indexed in Scilit:
- Real-time algorithms for string-matching and palindrome recognitionPublished by Association for Computing Machinery (ACM) ,1976
- On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown storePublished by Association for Computing Machinery (ACM) ,1976
- A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a StringJournal of the ACM, 1975
- Real-Time Simulation of Multihead Tape UnitsJournal of the ACM, 1972
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State MachinesIEEE Transactions on Computers, 1969
- On the minimum computation time of functionsTransactions of the American Mathematical Society, 1969
- Time and tape complexity of pushdown automaton languagesInformation and Control, 1968
- A One-Dimensional Real-Time Iterative MultiplierIEEE Transactions on Electronic Computers, 1965
- Uniqueness Theorems for Periodic FunctionsProceedings of the American Mathematical Society, 1965
- The equation $a^M=b^Nc^P$ in a free group.The Michigan Mathematical Journal, 1962