证明正则表达式学习在多种条件下都很难，即使在简单分布下也难学。
On the Hardness of Learning Regular Expressions
- 在PAC模型和成员查询下研究正则表达式学习的计算难度
- 即使在超立方体均匀分布下，学习仍困难，且无分布学习也难
- 扩展正则表达式含补集或交集后，学习难度依然高
尽管正则表达式在理论和实践中具有重要意义，但其学习的计算复杂性尚未得到充分探索。本文研究了在PAC模型和成员查询下不正确学习正则表达式的计算难度。结果表明，在超立方体上的均匀分布下，PAC学习仍然困难，并且证明了在无分布假设下使用成员查询的学习也是困难的。此外，当正则表达式扩展包含补集或交集操作时，即便在均匀分布下，学习问题依然困难。这些结论无法从已有针对确定有限自动机（DFA）或非确定有限自动机（NFA）的学习困难性结果中推出，因为正则语言在不同表示形式下的描述复杂度可能呈指数级差异。
原文摘要 · Abstract (English)
Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。