摘要
Kleinberg和Mullainathan [KM24]的最新工作为极限语言生成提供了一个具体的模型:给定来自未知目标语言的示例序列,目标是从目标语言生成新的示例,以便在某个点之后不会生成任何错误的示例。与密切相关的语言识别问题的强烈负面结果形成鲜明对比的是,他们为所有可数语言集合的极限语言生成建立了积极的结果。Raman和Tewari [RT24]的后续工作研究了算法在实现正确的语言生成之前所需的独特输入数量的界限——即,这对于集合中的所有语言是否都是一个常数(统一生成)还是一个依赖于语言的常数(非统一生成)。我们证明,每个可数语言集合都具有一个具有更强非统一极限生成属性的生成器。然而,虽然[KM24]的生成算法可以使用成员查询来实现,但我们证明任何算法都不能仅使用成员查询来非统一生成仅包含两个语言的集合。我们还通过引入穷举生成的定义,正式化了[KM24]生成算法中有效性和广度之间的张力,并展示了穷举生成的强烈负面结果。我们的结果表明,在极限生成中,有效性和广度之间的权衡是固有的。最后,受可以选择获取反馈的算法的启发,我们考虑了具有反馈的统一生成模型,根据集合的复杂性度量完全刻画了这种具有反馈的统一生成可能的语言集合。