Comments on: A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries https://icgi2020.lis-lab.fr August 23-27, 2021 Wed, 08 Dec 2021 05:57:07 +0000 hourly 1 https://wordpress.org/?v=7.1 By: Alex Clark https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-54 Wed, 25 Aug 2021 15:53:57 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-54 In reply to Makoto Kanazawa.

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

]]>
By: Makoto Kanazawa https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-37 Tue, 24 Aug 2021 12:32:18 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-37 In reply to Alex Clark.

Doesn’t that make all the A_i equivalent?

]]>
By: Alex Clark https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-36 Tue, 24 Aug 2021 08:54:27 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-36 In reply to Makoto Kanazawa.

So for every production B \to \alpha we have m productions of the form A_i \to \alpha.

]]>
By: Makoto Kanazawa https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-34 Tue, 24 Aug 2021 07:47:08 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-34 In reply to Alex.

I’m not sure how the suggestion goes. If G has an SPP whose B-component is a union of m sets of the form C_i^{\triangleleft} \cap D_i^{\overline{\triangleleft}}, are we supposed to replace B with m new nonterminals A_1, \dots, A_m so that a new SPP will have the set C_i^{\triangleleft} \cap D_i^{\overline{\triangleleft}} as its A_i-component? What will the productions be that have A_i as their left-hand side?

]]>
By: Alex https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-27 Mon, 23 Aug 2021 13:56:10 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-27 Nice work ! On the FCP(k,l,m) question, I have the intuition that the union of m components can be simulated using lots of rules using just m = 1 components.
i.e. if we have a nonterminal B = A_1 \cup \dots A_m then w can just expand out all the rules using B with rules using A_i etc,
But I think that may be incorrect?

]]>
By: Makoto Kanazawa https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-21 Mon, 23 Aug 2021 10:03:46 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-21 In reply to Rémi.

My original intuition was that of course more context-free languages are included because FC_L(k,l,m) contains many more sets than FC_L(k,l). But it’s very difficult to give examples of CFLs that differentiate the two. Perhaps you don’t get any more CFLs.

]]>
By: Makoto Kanazawa https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-20 Mon, 23 Aug 2021 10:01:10 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-20 In reply to Rémi.

Sound pre-fixed points work for both approaches. For the original primal approach, an SPP must consist of the closures of finite sets of strings. To generalize, you could think of changing either “closure” or “sets of strings”. There is some discussion in the concluding section of our paper. I can probably give more details during the Q/A period.

]]>
By: Makoto Kanazawa https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-19 Mon, 23 Aug 2021 09:57:30 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-19 Errata to the article: https://makotokanazawa.ws.hosei.ac.jp/publications/ICGI2021_errata.pdf

]]>
By: Rémi https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-7 Thu, 19 Aug 2021 09:38:18 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-7 I have another question: as far as I understand, you do not have a result to compare FCP(k,l) and FCP(k,l,m), or about the potential hierarchy within FCP(k,l,m). What’s your intuition?

]]>
By: Rémi https://icgi2020.lis-lab.fr/a-hierarchy-of-context-free-languages-learnable-from-positive-data-and-membership-queries/#comment-6 Thu, 19 Aug 2021 09:35:37 +0000 https://icgi2020.lis-lab.fr/?page_id=479#comment-6 This is a very impressive generalisation of distributional learning! Thanks you for this work.
Can one imagine a condition like the sounded pre-fixed in the primal approach? If yes, what may it looks like? If no, why ?

]]>