6
$\begingroup$

Are there any measures to compute similarity (or distance) between two DFAs?

If yes, which are the main references?

I need a measure of similarity, not only a (binary) equivalence test.

"Similarity" is an intuitive concept. There are different ways to formalize it; i'm looking for ready-to-use formalizations with regard to DFAs (not NFAs, weighted automata, or general graphs!). Furthermore, good solutions may exploit recognized languages.

I found some studies about this problem, which help to clarify the question. They involve two approaches: one from model-testing field aiming at compare languages, a second defined by authors aiming at compare structure of DFAs.

  • Bogdanov, Kirill, and Neil Walkinshaw. "Computing the structural difference between state-based models." Reverse Engineering, 2009. WCRE'09. 16th Working Conference on. IEEE, 2009.

  • Walkinshaw, Neil, Kirill Bogdanov, and Ken Johnson. "Evaluation and comparison of inferred regular grammars." Grammatical Inference: Algorithms and Applications. Springer Berlin Heidelberg, 2008. 252-265.

  • Walkinshaw, Neil, and Kirill Bogdanov. "Automated comparison of state-based software models in terms of their language and structure." ACM Transactions on Software Engineering and Methodology (TOSEM) 22.2 (2013): 13.

They compute exactly what I was looking for, a metrics among DFAs, adopting the techniques developed in the model-testing field.

Does there exist any other approaches, ready-to-use, to compute similarity between DFAs? (Both in terms of language both of structure).

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ I don't see how you could define a universal similarity measure. Do you have an application in mind? $\endgroup$ – adrianN Apr 20 '16 at 10:26
  • $\begingroup$ Relate to the symmetric difference of their languages? Which is regular too, and also has a DFA. $\endgroup$ – Hendrik Jan Apr 20 '16 at 10:50
  • 1
    $\begingroup$ (at)adrianN I think it is a application-independent problem, automata theory is an rich autonomous field of studies. Furthermore, some equivalence-tests among DFAs exist (such as Wp-method), but they depend on a sampling of automata (building examples of recognized languages). I'm looking for something based on DFA features. @HendrikJan It could be a way, but symmetric difference is more related to language recognized by DFAs then to automata features. In the cases where i've only automata, I should sampling the languages to compute the sym. diff., but I don't want to work with languages. $\endgroup$ – Gabrer Apr 20 '16 at 12:36
  • $\begingroup$ Similarity between the DFAs or between the languages they accept? $\endgroup$ – David Richerby Apr 20 '16 at 15:09
  • 1
    $\begingroup$ I think the question can be improved by expanding upon which kind of measures you found and which aspects you'd want alternatives for. Reopening, though, because I think it's more clear now what the question is. (cc @DavidRicherby) $\endgroup$ – Raphael♦ May 11 '16 at 15:08
9
$\begingroup$

This problem seems to ask for co-development of a reasonable distance function and an algorithm to compute it for a given pair of languages.

The paper "The Cost of Traveling between Languages" by Michael Benedikt, Gabriele Puppis, and Cristian Riveros defines one such notion, where we are searching for the largest value $d$ such that there exists a word $w$ in the language of the first automaton such that the edit distance of $w$ to any word in the second language is at least $|w| \cdot d$. The paper gives an algorithm to solve this problem, which involves distance automata.

The paper also has an interesting related work section, with a reference to the paper "Edit-distance of weighted automata: general definitions and algorithms" by Mohri, which seems to solve the same problem without the multiplication with the word length.

Both of these definitions are reasonable from a theoretical point of view - you now only have to evaluate whether they make sense for your particular application.

Both of the paper have author-archived versions available without pay-wall on the web which you should easily find with your favorite search engine.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the hints, but I can't accept as answer because they are just a possibile ways that need to be expanded to cope the problem of metric among DFAs. $\endgroup$ – Gabrer May 9 '16 at 11:59
  • $\begingroup$ @reinierpost: If you see the references I added, you will see that problem of similarity is directly addressed. For instance: if someone suggest me to follow a graph strategy, suggesting to see for biparted graphs, I can't accept too. Because it is a possibile strategy, but it hasn't been developed yet. I don't want to create/develop a new method to compare DFAs, I want to find a list of ready-to-use methods, as the reported pointed out in the provided references. $\endgroup$ – Gabrer May 9 '16 at 13:49
0
$\begingroup$

I accepted the DCTLib's answer because is the best-one so far.

Here, I will add some other references that I am going to find during my researche and which satisfy the need of a ready-to-use metric/algorithm for intuitive notion of similarity between DFAs.

  • Van den Bos et al. "Enhancing Automata Learning by Log-Based Metrics".
    From abstract: << We study a general class of distance metrics for deterministic Mealy machines. [...] By choosing an appropriate weight function we may fine-tune our metric so that it captures some intuitive notion of quality.>>
| cite | improve this answer | |
$\endgroup$

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.