論文の概要: Active Learning of Symbolic Automata Over Rational Numbers
- arxiv url: http://arxiv.org/abs/2511.12315v1
- Date: Sat, 15 Nov 2025 18:04:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-18 14:36:23.885091
- Title: Active Learning of Symbolic Automata Over Rational Numbers
- Title（参考訳）: 記号型オートマタの有理数上での能動的学習
- Authors: Sebastian Hagedorn, Martín Muñoz, Cristian Riveros, Rodrigo Toro Icarte,
- Abstract要約: Angluinの$L*$アルゴリズムは、必要最低限の教師が与えられたときに有限状態オートマトン(DFAs)を学習する。
我々は$L*$を拡張して、遷移が有理数、すなわち無限かつ高密度なアルファベット上の述語を使用するシンボリックオートマトンを学ぶ。
提案アルゴリズムは,遷移数に対して最も線形な教師に対して,述語の表現サイズに関して,質問数を求めるという意味で最適である。
- 参考スコア（独自算出の注目度）: 4.921484415160938
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the $L^*$ algorithm, introduced by Angluin. The $L^*$ algorithm learns deterministic finite-state automata (DFAs) in polynomial time when provided with a minimally adequate teacher. Unfortunately, the $L^*$ algorithm can only learn DFAs over finite alphabets, which limits its applicability. In this paper, we extend $L^*$ to learn symbolic automata whose transitions use predicates over rational numbers, i.e., over infinite and dense alphabets. Our result makes the $L^*$ algorithm applicable to new settings like (real) RGX, and time series. Furthermore, our proposed algorithm is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the number of transitions, and to the representation size of the predicates.
- Abstract（参考訳）: オートマタ学習は人工知能とソフトウェア工学に多くの応用がある。
これらのアプリケーションの中心は、Angluinによって導入された$L^*$アルゴリズムである。
L^*$アルゴリズムは、決定論的有限状態オートマトン(DFAs)を多項式時間で学習する。
残念ながら、$L^*$アルゴリズムは有限アルファベット上のDFAしか学習できないため、適用性は制限される。
この論文では、遷移が有理数、すなわち無限で高密度なアルファベット上の述語を使用するシンボリックオートマトンを学ぶために$L^*$を拡張する。
この結果から,(実)RGXや時系列といった新しい設定に,$L^*$アルゴリズムを適用した。
さらに, 提案アルゴリズムは, 遷移数に対して最も線形な教師に対して, 述語の表現サイズに関して, 質問数を求めるという意味で最適である。
関連論文リスト
- RaaS: Reasoning-Aware Attention Sparsity for Efficient LLM Reasoning [14.409253716114213]
大規模言語モデル(LLM)は、様々な領域にまたがる強力な機能を示している。
これらのアルゴリズムは、正確さ、時間、記憶の「不可能なトリニティ」に苦しむ。
本稿では,マイルストーントークンを識別し,KVベクトルを不要になるまで保持するアルゴリズム RaaS を提案する。
論文 参考訳（メタデータ） (2025-02-16T14:28:52Z) - Active Learning of Mealy Machines with Timers [3.087487671441056]
ブラックボックスのコンテキストでタイマーでMealyマシンをクエリする最初のアルゴリズムを提案する。
我々のアルゴリズムはVaandragerらのL#アルゴリズムを時間設定に拡張したものである。
論文 参考訳（メタデータ） (2024-03-04T13:20:52Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning [9.594432031144716]
アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。
NPハードな定性推論問題を解くための新しい枠組みを提案する。
我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
論文 参考訳（メタデータ） (2023-05-25T11:45:12Z) - Automatically Bounding the Taylor Remainder Series: Tighter Bounds and
New Applications [10.824474741383723]
テイラー剰余級数を自動的に有界化するための新しいアルゴリズムを提案する。
我々のアルゴリズムは機械学習ハードウェアを効率的に利用することができ、JAX.NETのオープンソース実装を提供しています。
コンパニオンペーパーでは、我々の新しい機械を用いて、最初の普遍的偏化最小化最適化アルゴリズムを作成する。
論文 参考訳（メタデータ） (2022-12-22T00:43:06Z) - Algorithms for Weighted Pushdown Automata [96.29471304123844]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-13T10:21:31Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。