With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?

  • $\begingroup$ Distance metrics are mainly problem-specific. There are many known strings metrics. If you described (in your OP) specifics of your problem and what you have done, maybe people could be more helpful. Also, here is a bioinformatics related article that uses grammar-based metrics to cluster large sets of 16S sequences. $\endgroup$ – fade2black Sep 7 '17 at 0:37
  • $\begingroup$ Sure there are many distance definition that induce a metric space over string, my question is, if there are any distance over regular expressions $\endgroup$ – Santiago Hincapie Sep 7 '17 at 1:43
  • $\begingroup$ Yes, there are distance metrics. For instance, consider the following metric: $d(R,R') = 0$ if regular expressions $R,R'$ accept the same language, otherwise $d(R,R')=\infty$. That's a distance metric. That's probably not helpful, though. I suspect you're not asking the right question. What properties do you want the distance metric to have? How do you plan to use it? Why are you asking? What's your motivation/goal? I suggest editing the question to provide further context. In general, if your question fits into one or two sentences, it might better to tell us more. $\endgroup$ – D.W. Sep 7 '17 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.