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

Abstract

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.

Original languageEnglish
Pages520-529
Number of pages10
Publication statusPublished - 01.12.2007
EventInternational MultiConference of Engineers and Computer Scientists 2007
- Kowloon, Hong Kong
Duration: 21.03.200723.03.2007
Conference number: 100960

Conference

ConferenceInternational MultiConference of Engineers and Computer Scientists 2007
Abbreviated titleIMECS 2007
Country/TerritoryHong Kong
CityKowloon
Period21.03.0723.03.07

Fingerprint

Dive into the research topics of 'On the High-Level Synthesis of Combinational Circuits for Contiguous Pattern Matching'. Together they form a unique fingerprint.

Cite this