Skip to main content
Kent Academic Repository

Regular expression matching using associative memory

Tripp, Gerald (2010) Regular expression matching using associative memory. Technical report. , Canterbury, Kent. CT2 7NF. UK. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:30619)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://www.cs.kent.ac.uk/pubs/2010/3055

Abstract

This paper describes a method for the implementation of regular expression matching based on the use of a form of associative (or content addressable) memory. The regular expression matching is performed by converting the regular expression into a Deterministic Finite Automata, but then using associative memory to hold the state transition information. Rather than try to simplify the resulting automata, this approach starts from the point of view of each next state in the automata being arrived at from some particular area of state-input space. We implement our automata by defining a number of orthogonal regions of state-input space, each of which is compared against our current state and input data. The highest priority region that produces a match will identify a corresponding next state for the automata. This work differs from previous work in that the associative memory used performs a full set membership test, and is hence more selective than systems based on Ternary Content Addressable Memory. This report describes work in progress, which to date has produced the rule processing software and outline designs for the hardware.

Item Type: Reports and Papers (Technical report)
Uncontrolled keywords: determinacy analysis, Craig interpolants
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Gerald Tripp
Date Deposited: 21 Sep 2012 09:49 UTC
Last Modified: 16 Nov 2021 10:08 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/30619 (The current URI for this page, for reference purposes)

University of Kent Author Information

Tripp, Gerald.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.