Palindrome recognition in real time by a multitape Turing machine

DOI10.1016/0022-0000(78)90042-9zbMath0386.03020MaRDI QIDQ1249574

Zvi Galil

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90042-9

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D10: Turing machines and related notions

Related Items

Efficient string matching on packed texts, Counting distinct palindromes in a word in linear time, Efficient retrieval of approximate palindromes in a run-length encoded string, Parallel detection of all palindromes in a string, Searching for gapped palindromes, The derivation of on-line algorithms, with an application to finding palindromes, Palindrome recognition using a multidimensional tape., Searching for Gapped Palindromes, Real-time recognition of substring repetition and reversal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
• Iterative arrays with direct central control
• Real time computation
• String Matching in Real Time
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast Pattern Matching in Strings
• On the Computational Complexity of Algorithms
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-Time Simulation of Multihead Tape Units