Comments on: Learning DFAs by Evolving Short Sequences of Merges https://icgi2020.lis-lab.fr August 23-27, 2021 Tue, 31 Aug 2021 11:13:08 +0000 hourly 1 https://wordpress.org/?v=7.1 By: John Abela https://icgi2020.lis-lab.fr/learning-dfas-by-evolving-short-sequences-of-merges/#comment-57 Fri, 27 Aug 2021 12:34:25 +0000 https://icgi2020.lis-lab.fr/?page_id=520#comment-57 Hello Francois,

You are absolutely right. Empirical observation is not a proof. We have observed that if we colour the states of the target a DFA and then colour also the states of the APTA using the colours from the target DFA then we can run EDSM, or any other meta heuristic, and be able to determine when, and perhaps why, EDSM works and, perhaps more importantly, when and why it fails.

When each state in the APTA is coloured and fully labeled (accepting or non-accepting) then EDSM always (observed over 10’s of thousands of experiments) finds the target DFA in n+1 merges.

Therefore, proving that there is always a n+1 state merging path from the APTS to the DFA is equivalent to showing that EDSM will always find the target DFA from a coloured, and fully labelled, APTA. Of course, it is assumed that the training set is structurally complete.

We do not have a proof yet but we have been busy with other things. Kris and I had a long chat today and we will be looking into finding a proof for this result in the next weeks.

Regards,

John

]]> By: François Coste https://icgi2020.lis-lab.fr/learning-dfas-by-evolving-short-sequences-of-merges/#comment-56 Fri, 27 Aug 2021 09:44:39 +0000 https://icgi2020.lis-lab.fr/?page_id=520#comment-56 You observed it, but do you think that you could also prove that there is always a n+1 state merging path from APTA to target DFA? What would you guess to be then the required conditions (structural completeness obviously, and maybe some characteristic set properties to ensure uniqueness…) ?

]]>