Designing Combinational Circuits for Scattered Pattern Matching


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.

Original languageEnglish
Number of pages9
Publication statusPublished - 01.12.2007
Event22nd International Conference on Computers and Their Applications 2007 - Honolulu, United States
Duration: 28.03.200730.03.2007
Conference number: 98930


Conference22nd International Conference on Computers and Their Applications 2007
Abbreviated titleCATA 2007
Country/TerritoryUnited States


Dive into the research topics of 'Designing Combinational Circuits for Scattered Pattern Matching'. Together they form a unique fingerprint.

Cite this