Pattern matching and applications

Abstract

Pattern matching as related to string matching finds extensive application. One of the most interesting problems often encounterd in string matching is that of string compression, i.e., to find the shortest possible string that contains every string in a given set as substrings. Such a shortest possible string is called a SHORTEST COMMON SUPERSTRINGS (SCS). Algorithms for developing the SCS have been investigated. The SCS problem is NP-complete, meaning that there is no polynomial-time algorithm to solve this problem. Hence polynomial-time approximation algorithms have been investigated. We have proposed the Graph-Reduction Algorithm which lends itself to heuristic solutions and could possibly be used for implementation by hardware. The Graph-ReductionAlgorithm proposed for SCS has been applied to the generation of test sequences called checking experiments for sequential machines. The SCS method referred to as the Supersequence Construction Method is shown to yield shorter length checking experiments than the conventional method based on Hennie's procedure. Finally as a first step towards a hardware solution for the SCS, an efficient implementation of a special-purpose VLSI chip has been given to find overlaps between strings. The chip has been designed as systolic array. A VLSI implementation of the basic cells has been carried out in CMOS.