A Linear-Time On-Line Recognition Algorithm for ``Palstar

DOI10.1145/322047.322056zbMath0365.68058OpenAlexW2006238893WikidataQ108435906 ScholiaQ108435906MaRDI QIDQ4140392

Joel I. Seiferas, Zvi Galil

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322047.322056

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

Palindromic decompositions with gaps and errors ⋮ EERTREE: an efficient data structure for processing palindromes in strings ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Counting the palstars ⋮ Steady-paced-output and fractional-on-line algorithms on a RAM ⋮ Palindromic Decompositions with Gaps and Errors ⋮ Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays ⋮ Detecting One-Variable Patterns ⋮ Counting Palindromes in Substrings ⋮ Finding maximal 2-dimensional palindromes ⋮ Parallel detection of all palindromes in a string ⋮ Finding Palindromes: Variants and Algorithms ⋮ Unnamed Item ⋮ Palindromic rich words and run-length encodings ⋮ Detecting leftmost maximal periodicities ⋮ Tight tradeoffs for real-time approximation of longest palindromes in streams ⋮ The derivation of on-line algorithms, with an application to finding palindromes