The derivation of on-line algorithms, with an application to finding palindromes

DOI10.1007/BF01182773zbMath0818.68081WikidataQ56458981 ScholiaQ56458981MaRDI QIDQ1314430

Johan Jeuring

Publication date: 16 February 1994

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

program transformationsBird-Meertens calculuslongest palindromic substringmaximal palindromes

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Specification and verification (program logics, model checking, etc.) (68Q60) General topics in the theory of software (68N01)

Related Items

Time-Space Trade-Offs for Longest Common Extensions, A subquadratic algorithm for minimum palindromic factorization, HV-Palindromes in Two-Dimensional Words, Time-space trade-offs for longest common extensions, Finding Palindromes: Variants and Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data structures and program transformation
• Recognizing a symmetry predicate by multihead Turing machines with input
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
• Palindrome recognition in real time by a multitape Turing machine
• Formal derivation of a pattern matching algorithm
• String Matching in Real Time
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• Fast Pattern Matching in Strings
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines