In several papers I have read that Bit-parallel pattern matching is an NFA-simulation.

My questions are:

1- Is it true in general? Or, is there any restrictions?

2- As any regular expression can be converted to NFA, how Bit-parallelism is able to handle some regex like: a?5

Update: Bit-parallel pattern matching is a family of well-known pattern matching algorithms in the literature of hardware-based pattern matching. It was introduced by Baeza-Yates and Gonnet (A New Approach to Text Searching, Communications of the ACM, 35(10):74–82, 1992; PDF) and has gained more attention recently, for example in Faro and Lecroq, Twenty Years of Bit-Parallelism in String Matching (Festschrift for Bořivoj Melichar, pp. 72–101; PDF).

In these papers there are several statements like: "Bit-parallelism is indeed particularly suitable for the eefficient simulation of non-deterministic automata.", second reference, page 2.

  • 4
    $\begingroup$ I'm not sure what you mean by either "bit parallel pattern matching" or how that would be "an NFA-simulation" (NFAs should be understood by anyone who's taken a CS course but it's not obvious how you're simulating them). Could you expand your question a little to clarify? If you think these concepts are really widely known and I'm just being dumb and/or ignorant, I'd suggest a one-sentence summary and a link to a reference would be plenty. $\endgroup$ – David Richerby Nov 5 '15 at 10:14
  • 1
    $\begingroup$ @DavidRicherby I have updated the question. since I am new here, I was not able to add more references. $\endgroup$ – MH Samadani Nov 6 '15 at 10:23
  • $\begingroup$ you can add as many text references as you like & plz do (but maybe SE is restricting the URLs for low rep users)? as for their assertions, are they offhand, do they have any other related analysis/ thms etc? $\endgroup$ – vzn Nov 6 '15 at 17:06

on p4-5 of your 2nd ref by Faro and Lecroq they write:

Online string matching algorithms (hereafter simply string matching algorithms) can be divided into three classes: algorithms which solve the problem by making use only of comparisons between characters, algorithms which make use of deterministic automata and algorihtms which simulate nondeterministic automata using bit-parallelism.

however, while sounding general, these statements seem to be wrt "within the realm of string matching algorithms". in other words there is massive use/ research of bit parallelism of NFAs for string matching algorithms in particular, but have not seen much bit parallelism ideas applied to arbitrary NFAs, even though it is clearly applicable. here are two refs turned up that do consider bitwise operations on a more general/ arbitrary case (apparently the focus of your question). in the 2nd case, "vector algorithms" are capable of/ nearly the same as "bit parallelism".

  • 1
    $\begingroup$ Thanks. I actually mean in the realm of string matching. I want to know that if bit-parallelism can simulate any NFAs in for string matching? If so, how it can be used to evaluate my example. Clearly it can represent characters, compliments, classes and wildcard, but how it can be used to represent the match-zero-or-more operator? $\endgroup$ – MH Samadani Nov 8 '15 at 7:17
  • $\begingroup$ answer is a best attempt to answer your question as you wrote it, not nec as it was intended... the statement about wide use of bit parallelism for string matching NFAs is strongly supported by a lot of literature incl the exact same refs you cite... yes there are some restrictions... may look into this further... $\endgroup$ – vzn Nov 8 '15 at 16:47

Your Answer

