Thanks for this very nice question!
I would say that regular expressions are harder to learn than LTL formulas, especially simple fragments of LTL as we consider in this work. One of the reason may be that LTL formulas reads words process words from left to right; this simple property implies that finding small LTL formulas can somehow be attacked with dynamic programming. Concretely: as shown in the paper, we can characterise the smallest LTL separating formula of the LTL(X, and) fragment, which is combinatorially way too difficult for regular expressions.

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

Oh I am wrong here; the reduction doesn’t work.
I don’t see how to construct an example though.

Thank you very much for the pointers, which look very interesting!

It seems that ELLs and VPLs are incomparable, as witnessed by the set of palindromes (which is not a VPL) and the Dyck language (which is not an ELL). As the rules of visibly pushdown grammars and even linear grammars are similar and only differ in two aspects (while VPLs are non-linear, they restrict the use of terminal symbols), it would be interesting to see whether learning techniques from one class can be transferred to the other to obtain algorithms for richer classes of grammars.

Thank you very much for the kind feedback and the interesting question!

Unfortunately, we do not yet have a practical comparison with the more direct approaches. These direct algorithms are indeed likely to be suitable for the task of grammar extraction from the RNNs, too. Depending on the target language, they may require fewer queries since the canonical object they learn is potentially smaller. It would be very worthwhile to perform an experimental evaluation of the number of queries required by these algorithms with respect to the VPLs considered in this work.

It seems that ELLs and VPLs are incomparable, as witnessed by the set of palindromes (which is not a VPL) and the Dyck language (which is not an ELL). As the rules of visibly pushdown grammars and even linear grammars are similar and only differ in two aspects (while VPLs are non-linear, they restrict the use of terminal symbols), it would be interesting to see whether learning techniques from one class can be transferred to the other to obtain algorithms for richer classes of grammars.

Thank you for your response and explanation in Q&A session! It’s clear to me. Thank you!