Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data
International Conference on Grammatical Inference,
Proceedings of Machine Learning Research Vol.217, pp.23-34
(2023), [peer-reviewed]
Event Date:
July 10-13, 2023
@ Rabato, Morocco
- Rabato, Morocco
Abstract / 概要
This paper is concerned with the identification in the limit from positive data of substitutable context-free languages CFLs over infinite alphabets. [ClarkE07] showed that substitutable CFLs over finite alphabets are learnable in this learning paradigm. We show that substitutable CFLs generated by grammars whose production rules may have predicates that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to [ArgyrosDA2018]’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some CFLs in the limit from positive data.