Correctness and efficiency of pattern matching algorithms

DOI10.1016/0890-5401(91)90046-5zbMath0738.68034OpenAlexW2071907974MaRDI QIDQ1183611

Livio Colussi

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90046-5

zbMATH Keywords

program correctnesscorrectness proofsworst caseprogram developmentprogram efficiencyalgorithm of Knuth, Morris, and Prattformal verification of programsHoare axiomatic semantics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Light-based string matching ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ A simple fast hybrid pattern-matching algorithm ⋮ On-line string matching algorithms: survey and experimental results ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ Tight comparison bounds for the string prefix-matching problem ⋮ Improved pattern-scan-order algorithms for string matching ⋮ Fast string matching for DNA sequences ⋮ A New String Matching Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An axiomatic definition of the programming language Pascal
• A fast string searching algorithm
• Recursion As an Effective Step in Program Development
• Saving Space in Fast String-Matching
• A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
• Fast Pattern Matching in Strings