Real-time recognition of substring repetition and reversal

DOI10.1007/BF01768472zbMATH Open0349.68035OpenAlexW1985572507MaRDI QIDQ4120141FDOQ4120141

Zvi Galil, Joel I. Seiferas

Publication date: 1977

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01768472

Mathematics Subject Classification ID

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

Cites Work

• The equation \(a_ M=b^ Nc^ P\) in a free group
• Fast Pattern Matching in Strings
• Uniqueness Theorems for Periodic Functions
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Palindrome recognition in real time by a multitape Turing machine
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-Time Simulation of Multihead Tape Units
• On the Minimum Computation Time of Functions
• Title not available (Why is that?)

Cited In (5)

• Detecting leftmost maximal periodicities
• Simple real-time constant-space string matching
• A simplified proof of the real-time recognizability of palindromes on Turing machines
• Time-space-optimal string matching
• Simple Real-Time Constant-Space String Matching

This page was built for publication: Real-time recognition of substring repetition and reversal

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