本論文では、次のシンボル予測（NSP）設定における言語の学習可能性を研究しています。この設定では、学習者は言語からの正の例しか受け取らず、各接頭辞に対して、それが言語に含まれるかどうかと、その接頭辞から受理される文字列に繋がる次のシンボルが何かを学ぶ必要があります。NSP設定は、以前の研究でニューラルシーケンスモデルの実証分析に使われており、効率的なアルゴリズムが言語モデルの（切り捨てた）サポートを学習するためにも利用できることが示されています。多くのラベルを利用できるにもかかわらず、DFA（決定性有限オートマトン）やブール式のような概念クラスの学習は依然として計算的に困難であることを証明しています。この証明は、ほとんどの追加ラベルが有益でないように構築されており、従来の学習問題からNSPラベルでの学習への還元を導きます。暗号的仮定のもと、この還元は、NSP設定におけるDFA学習の困難性を示唆しています。