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

DOI10.1016/0020-0190(76)90050-8zbMATH Open0328.68047OpenAlexW1972674211MaRDI QIDQ1226857FDOQ1226857

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

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

Cites Work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast on-line integer multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

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

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

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