13
$\begingroup$

I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be close if they don't differ by many words. We could also use the edit distance in some way... I could not find good references on this issue.

I don't call it a distance because I don't require all the distance axioms to be true (although it's not bad if they are).

A first attempt is to define $$d(L,K)= \limsup_{n\to\infty} \frac{|L_n\Delta K_n|}{|L_n\cup K_n|}$$ where $L_n$ and $K_n$ are the restrictions of $L$ and $K$ to $\Sigma^n$, and $\Delta$ is the symmetric difference.

Is this "distance" studied? Are there references on the subject (possibly with alternative choices for distance function)? Any help or pointer would be appreciated, thanks.

$\endgroup$
11
$\begingroup$

As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:

$$ d(l, k) = \left\{ \begin{array}{ll} 0 & \mbox{if } l = k \\ 2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\} \end{array} \right. $$

Roughly speaking, if a string is a sequence of events, the distance between two strings is $2^{-n}$, where $n$ is the first time they differ. This can be lifted to a metric on (nonempty) languages by using the Hausdorff metric. (If you allow infinite strings, you also have to ensure that the languages are Cauchy-complete.)

This metric shows up a lot in verification. The first reference to this that I know is Alpern and Schneider 1985, Defining Liveness. (Sorry for the absence of a link, but I couldn't find an online copy.)

Jean-Eric Pin has written a survey article, Profinite Methods in Automata Theory, in which he surveys some more general metrics, and also draws some connections to Stone duality.

$\endgroup$
  • $\begingroup$ Thanks, I was aware of Cantor metric, but not of its use for defining the Hausdorff metric, this seems perfectly fine. $\endgroup$ – Denis Jun 3 '13 at 14:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.