Cep NFA formal declaration

[Bence Ágocsi Kiss]

Hi,

I'm trying to use the CEP library, and for that, i've read the tutorial on the site and I tried the given examples. However, I would need a more accurate description to understand the behavior. I haven't found any formal description, about how the NFA works, and how they are built from the pattern language. I would really appreciate that, if somebody could give an paper or some formal explanation of its mechanism

Thanks and regards

Bence Agocsi-Kiss

[Till Rohrmann]

Hi Bence,

Flink's CEP implementation is mainly based on this paper [1]. It mainly describes how the shared buffer is used to store efficiently the internal state of the NFA. 

The translation of the Pattern API into the NFA happens in the NFACompiler.compileFactory method. For every pattern entry, we create a NFA state and insert transition between these states with the corresponding constraints. In case of a followedBy relation, we additionally add a reflexive transition where we ignore the current input symbol.

I hope this helps you a bit to better understand the implementation.

[1] https://people.cs.umass.edu/~yanlei/publications/sase-sigmod08.pdf

Cheers,

Till

On Thu, Jul 7, 2016 at 1:00 PM, Bence Ágocsi Kiss <[hidden email]> wrote:

Hi,

I'm trying to use the CEP library, and for that, i've read the tutorial on the site and I tried the given examples. However, I would need a more accurate description to understand the behavior. I haven't found any formal description, about how the NFA works, and how they are built from the pattern language. I would really appreciate that, if somebody could give an paper or some formal explanation of its mechanism

Thanks and regards

Bence Agocsi-Kiss