Two fast simulations which imply some fast string matching and palindrome-recognition algorithms

DOI10.1016/0020-0190(76)90050-8zbMath0328.68047OpenAlexW1972674211MaRDI QIDQ1226857

Zvi Galil

Publication date: 1976

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(76)90050-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10) Algorithms in computer science (68W99)

Related Items (8)

The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ On time versus space. II ⋮ Parallel detection of all palindromes in a string ⋮ Finding all the palindromes in a binary tree in linear time and space ⋮ Palindrome recognition in real time by a multitape Turing machine ⋮ Minimizing access pointers into trees and arrays ⋮ On linear context-free languages and one-way multihead automata ⋮ The derivation of on-line algorithms, with an application to finding palindromes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast on-line integer multiplication

This page was built for publication: Two fast simulations which imply some fast string matching and palindrome-recognition algorithms