論文の概要: The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

• arxiv url: http://arxiv.org/abs/2605.30389v1
• Date: Thu, 28 May 2026 11:19:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-01 20:56:50.134858
• Title: The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
• Title（参考訳）: パターン言語の包含深さ:アルゴリズム学習理論におけるオープンな問題
• Authors: Wei Luo,
• Abstract要約: この注記は、パターン言語の包含深さを計算する問題の定式化である。 中心的な開問題は、包含深さ ID_Sigma(p) が任意の有限アルファベット Sigma 上のすべてのパターン p に対して計算可能であるかどうかである。 単純な予想式 ID_Sigma(p) = 2|p| - #var(p) - 1 は線形時間アルゴリズムを意味する。
• 参考スコア（独自算出の注目度）: 7.317669651319179
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated by a given pattern. Inclusion depth captures the mind-change complexity of pattern identification from positive data. The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma with at least two symbols, and whether it is computable in polynomial time. A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm. The problem connects pattern language inclusion, combinatorics on words, language identification in the limit, and mind-change-bounded learning.
• Abstract（参考訳）: パターン言語は形式言語理論とアルゴリズム学習理論の古典的なモデルである。 このノートは、パターン言語から与えられたパターンによって生成された言語への、最も長い厳密な包含鎖の長さという、パターン言語の包含深さを計算することの問題を定式化する。 包含深度は、正のデータからパターン識別のマインド・チェンジの複雑さを捉える。 中心的な開問題は、包含深さ ID_Sigma(p) が少なくとも2つの記号を持つすべての有限アルファベット Sigma 上のすべてのパターン p に対して計算可能かどうか、多項式時間で計算可能かどうかである。 単純な予想式 ID_Sigma(p) = 2|p| - #var(p) - 1 は線形時間アルゴリズムを意味する。 この問題は、パターン言語の包摂性、単語のコンビネータクス、限界における言語識別、マインド-チェンジ-バウンドラーニング(マインド-チェンジ-バウンドラーニング)とを結びつけている。

関連論文リスト

• Logic-of-Thought: Empowering Large Language Models with Logic Programs for Solving Puzzles in Natural Language [67.51318974970985]
  自然言語でパズルを解くことは、AIにおける長年の課題である。 本稿では,大規模言語モデルを論理プログラミングでブリッジするフレームワークであるLogic-of-Thoughtを提案する。 動作を含む様々なグリッドパズルや動的パズルについて評価し、全てのタスクにおいてほぼ完璧な精度を示す。
  論文  参考訳（メタデータ） (2025-05-22T01:37:40Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• Are Language Models Puzzle Prodigies? Algorithmic Puzzles Unveil Serious Challenges in Multimodal Reasoning [24.386388107656334]
  本稿では,視覚的質問応答の文脈内での多モーダルパズル解決の新たな課題を紹介する。 本稿では,アルゴリズムパズルの解法におけるマルチモーダル言語モデルの能力に挑戦し,評価するための新しいデータセットAlgoVQAを提案する。
  論文  参考訳（メタデータ） (2024-03-06T17:15:04Z)
• Implementing Dynamic Programming in Computability Logic Web [0.0]
  本稿では,アルゴリズムとその対応するアルゴリズム言語であるCoLwebについて述べる。 CoLwebは、非分散コンピューティングと分散コンピューティングの両方のためのアルゴリズム設計に対して、高レベルの、証明付き、分散スタイルのアプローチを強制します。 我々は,Hhorn節の定義を視覚的ユニバーサリー量子化(BUQ)と並列ユニバーサリー量子化(PUQ)の2種類に洗練する。
  論文  参考訳（メタデータ） (2023-04-04T05:33:43Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  機械学習システムが問題を過度に考えずに論理的外挿を行う方法を示す。 本稿では,問題インスタンスの明示的なコピーをメモリに保持して,それを忘れないようにするリコールアーキテクチャを提案する。 また、モデルが数に固有の行動を学ぶのを防ぎ、無期限に繰り返される行動を学ぶためにモデルをプッシュするプログレッシブトレーニングルーチンも採用しています。
  論文  参考訳（メタデータ） (2022-02-11T18:43:28Z)
• Learning Union of Integer Hypercubes with Queries (Technical Report) [0.0]
  本稿では,d次元整数格子上での整数ハイパーキューブの有限和を求める問題について検討する。 非固定次元において、問題はDNF式を学習する問題を仮定する。 我々の問題には、量化子なし整数線型算術公式のモナディック分解問題への自然な応用がある。
  論文  参考訳（メタデータ） (2021-05-27T11:39:10Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)
• A Simple Joint Model for Improved Contextual Neural Lemmatization [60.802451210656805]
  本稿では,20言語で最先端の成果を得られる,単純結合型ニューラルモデルを提案する。 本論文では,トレーニングと復号化に加えて,本モデルについて述べる。
  論文  参考訳（メタデータ） (2019-04-04T02:03:19Z)

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

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