Palindrome recognition in real time by a multitape Turing machine

DOI10.1016/0022-0000(78)90042-9zbMath0386.03020OpenAlexW2012485168MaRDI 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

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (9)

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

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

This page was built for publication: Palindrome recognition in real time by a multitape Turing machine