A combinational module for scattered pattern matching tests whether the digits of a given pattern occur in the proper order and multiplicity within a given search string. We present a unifying high-level synthesis of linear and tree-structured combinational networks for scattered 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.
|Number of pages
|Published - 01.12.2007
|22nd International Conference on Computers and Their Applications 2007 - Honolulu, United States
Duration: 28.03.2007 → 30.03.2007
Conference number: 98930
|22nd International Conference on Computers and Their Applications 2007
|28.03.07 → 30.03.07