Palindrome recognition in real time by a multitape Turing machine

DOI10.1016/0022-0000(78)90042-9MaRDI QIDQ1249574zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast Pattern Matching in Strings
• Iterative arrays with direct central control
• On the Computational Complexity of Algorithms
• Real time computation
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-Time Simulation of Multihead Tape Units
• String Matching in Real Time
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms

Cited in

(9)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1249574)