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).