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.

Interesting talk, it makes me think about related work, not needing tree automata:
– Grammatical inference for even linear languages based on control sets, Yuji Takada,
– A characterization of even Linear Languages and its application to the learning problem, Jose M. Sempere and Pedro García
– The grammatical inference problem for the Szilard languages of linear grammars, Erkki Mäkinen
Is there an equivalence between even linear CFG and VPA, or what would be the difference ?

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.