I want to implement regexp search via translation to deterministic automata, as a toy project.

TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the goal of translation to weighted deterministic automata? How to calculate a derivative of a weighted regexp complement?

While researching regular expressions on Google Scholar, I learned of some generalizations to regular expressions:

The first generalization are the generalized (or, often, extended) regular expressions: in addition to the usual concatenation, alternation/union and star/iteration/Kleene closure, these extended regular expressions admit the complement/negation and intersection operators from set theory. This doesn't increase the theoretic expressive power of regexp, but it can make the regexp much more concise. As far as I understand, these are best translated to DFA with Brzozowski derivatives and to NFA with Antimirov derivatives.

A problem with classic DFA (requiring other generalizations to classic regexp) is that it's difficult to use them for submatching or search, instead of just recognition/deciding. One way of surmounting this difficulty is with tagged regular expressions (TRE), which can be translated to tagged automata (TNFA and TDFA).

Another possible solution are weighted regular expressions (AKA regular expressions with multiplicity). There seem to be multiple different definitions, but the gist of it is that instead of associating a boolean value with each string, weighted regular expressions associate a value from some semiring with each string, and they can be translated to weighted automata, with weights from the semiring on their edges/transitions.

This regexp generalization seems more mathematical, and more powerful in general than basing my implementation on TDFA. For example: apart from submatch extraction, weighted regexp can be used for fuzzy search and many other things (given an appropriate semiring) AFAIK.

My problem at this point seems to be combining extended regexp with weighted regexp, which would probably mean that I need an algorithm for calculating derivatives of weighted extended regexp. I did manage to find a paper describing derivatives of weighted regexp (Derivatives of rational expressions with multiplicity, 2005), but it doesn't cover extended regular expressions (i.e., the regexp as defined in the paper don't admit the complement operator).

So how do I translate weighted regular expressions with complement to deterministic weighted automata?

  • $\begingroup$ How do you define complement of a weighted automaton? $\endgroup$
    – pcpthm
    Mar 5, 2022 at 3:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.