Character search Algorithm

[Donald 'Paddy' McCarthy]

Hi,
My problem is I'm trying to learn about the implementation of assertion
languages like PSL/Sugar in digital logic simulators.
The assertion language allows you to more easily say "if this signal
combination/sequence follows that signal combination/sequence then ..."
I feel that you should be able to think of this as the simulator
providing a stream of signal values over simulator time that could be
translated into a string of characters interleaved with clock cycle
markers. Then the temporal assertion could be translated into a regular
expression acting on the string.

When I make the mental analogy above, then I think of the practicle
problems of such an implementation. The first is, if you have a finite
bounded re - e.g. no infinite matches i.e. no plus or star characters in
the RE, but you have a simulator churning out a huge sequence of
characters, how do you do the RE match efficiently?

I am thinking of a program skeleton that looks something like this

psl_re = PSL_subset_to_RE(PSL)
simulator.start(psl_re.clock, psl_re.signals_to_capture)
for cycles_psl_signals in simulator.next_cycle():
if psl_re.optimised_search(cycles_psl_signals):
raise PSL_PRE_CONDITION_FOUND

It is the psl_re.optimised_search() routine that I am after.
Is there any way of computing how big a string buffer needs to be (call
it B), so that you could then maybe keep a sliding buffer of a minimum
of just the last 2*B characters, sliding along and matching in B
character increments and guarantee to find the matches?

Help, or alternative algorithms would be appreciated.

Thanks, Paddy.