論文の概要: On the Hardness of Learning Regular Expressions

• arxiv url: http://arxiv.org/abs/2510.04834v1
• Date: Mon, 06 Oct 2025 14:17:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.893081
• Title: On the Hardness of Learning Regular Expressions
• Title（参考訳）: 正規表現学習の難しさについて
• Authors: Idan Attias, Lev Reyzin, Nathan Srebro, Gal Vardi,
• Abstract要約: ハイパーキューブの均一分布下においても,PAC学習は困難であることを示す。 また,メンバシップクエリによる分散自由学習の難しさも証明する。
• 参考スコア（独自算出の注目度）: 39.695696662928476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: 正規表現の理論的重要性と幅広い実用性にもかかわらず、それらの学習の計算複雑性は、ほとんど解明されていない。 本研究では,PACモデルとメンバシップクエリによる正規表現を不適切に学習する際の計算困難さについて検討する。 PAC学習はハイパーキューブの均一分布下においても困難であり,また,メンバーシップクエリによる分布自由学習の難しさも証明している。 さらに,正規表現を補間あるいは交叉で拡張した場合,一様分布下であっても,メンバシップクエリによる学習の困難さを確立する。 DFA, NFA, 正規表現では, 正規言語の記述複雑性が指数関数的に異なるため, これらの結果が既存のDFAやNFAの学習難易度の結果に従わないことを強調する。

関連論文リスト

• Lean Formalization of Generalization Error Bound by Rademacher Complexity [5.114451899552168]
  我々は、Mathlib 4ライブラリの確率理論に基づいて、Lean 4定理証明器に対するRademacher複雑性を用いた一般化誤差を定式化する。 また、$L2$-regularizationモデルに対する一般化誤差の形式化を示す。
  論文  参考訳（メタデータ） (2025-03-25T12:40:43Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。 MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• Real-time Regular Expression Matching [65.268245109828]
  本稿では,有限状態オートマトン,正規表現マッチング,パターン認識,指数的爆破問題について述べる。 本稿では,正規言語の複雑なクラスに対する指数的爆破問題に対する理論的およびハードウェア的解法を提案する。
  論文  参考訳（メタデータ） (2023-08-20T09:25:40Z)
• Formal Mathematics Statement Curriculum Learning [64.45821687940946]
  同じ計算予算、専門家の反復、つまり、学習にインターリーブされた証明検索が、証明検索のみを劇的に上回っていることを示す。 また, 難易度が十分に異なる形式文の集合に適用した場合, 専門家の反復により, ますます困難な問題に対するカリキュラムの発見と解決が可能であることも観察した。
  論文  参考訳（メタデータ） (2022-02-03T00:17:00Z)
• Iterated learning for emergent systematicity in VQA [3.977144385787228]
  ニューラルモジュールネットワークは構成性に対するアーキテクチャ上のバイアスを持っている。 レイアウトとモジュールを共同学習する場合、構成性は自動的に発生せず、適切な構造を示すレイアウトの出現には明示的な圧力が必要です。 本研究では,自然における構成言語の出現に関する認知科学理論である反復学習を用いてこの問題に対処することを提案する。
  論文  参考訳（メタデータ） (2021-05-03T18:44:06Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  PAC-セマンティックスにおける暗黙学習を拡張し、線形算術の言語における間隔としきい値の不確実性を扱う。 最適線形プログラミング対象制約の学習に対する我々の暗黙的アプローチは、実際的な明示的アプローチよりも著しく優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-23T19:08:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。