On the High-Level Synthesis of Combinational Circuits for Contiguous Pattern Matching

A combinational module for contiguous pattern matching tests whether the digits of a given pattern occur as a contiguous substring within a given search string. We present a unifying high-level synthesis of linear and tree-structured combinational networks for contiguous pattern matching based on the theory of list homomorphisms. From a predicate logic specification, we develop standard implementations for tree-structured modules processing the input digits of the search string in parallel. The tree-structured design is systematically specialized to iterative networks processing the search string sequentially from left to right or vice versa. The formal design is parameterized with the type of digits to be matched. Throughout the paper, we explicate functional methods for the structured description of combinational circuits with higher-order list functions.