論文の概要: RNN Generalization to Omega-Regular Languages

• arxiv url: http://arxiv.org/abs/2509.02491v1
• Date: Tue, 02 Sep 2025 16:40:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:04.107624
• Title: RNN Generalization to Omega-Regular Languages
• Title（参考訳）: メガ正規言語へのRNNの一般化
• Authors: Charles Pert, Dalal Alrajeh, Alessandra Russo,
• Abstract要約: 本稿では,リカレントニューラルネットワーク(RNN)が公式から派生した$omega$-regular言語に一般化できるかどうかを検討する。 RNNは、トレーニング例の最大8倍の長いシーケンスで評価した場合、ターゲットの$omega$-regular言語で高い精度が得られることを示す。
• 参考スコア（独自算出の注目度）: 46.54060985002888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: B\"uchi automata (BAs) recognize $\omega$-regular languages defined by formal specifications like linear temporal logic (LTL) and are commonly used in the verification of reactive systems. However, BAs face scalability challenges when handling and manipulating complex system behaviors. As neural networks are increasingly used to address these scalability challenges in areas like model checking, investigating their ability to generalize beyond training data becomes necessary. This work presents the first study investigating whether recurrent neural networks (RNNs) can generalize to $\omega$-regular languages derived from LTL formulas. We train RNNs on ultimately periodic $\omega$-word sequences to replicate target BA behavior and evaluate how well they generalize to out-of-distribution sequences. Through experiments on LTL formulas corresponding to deterministic automata of varying structural complexity, from 3 to over 100 states, we show that RNNs achieve high accuracy on their target $\omega$-regular languages when evaluated on sequences up to $8 \times$ longer than training examples, with $92.6\%$ of tasks achieving perfect or near-perfect generalization. These results establish the feasibility of neural approaches for learning complex $\omega$-regular languages, suggesting their potential as components in neurosymbolic verification methods.
• Abstract（参考訳）: B\"uchi Automatica (BA) は線形時間論理(LTL)のような形式仕様で定義された$\omega$-regular言語を認識し、リアクティブシステムの検証に一般的に使用される。 しかし、BAは複雑なシステムの振る舞いを扱い、操作する際にスケーラビリティの課題に直面します。 モデルチェックのような領域では、ニューラルネットワークがこれらのスケーラビリティの課題に対処するために使われるようになっているため、トレーニングデータを超えて一般化する能力を調べる必要がある。 この研究は、リカレントニューラルネットワーク(RNN)がLTL式から派生した$\omega$-regular言語に一般化できるかどうかを調査する最初の研究である。 我々は、最終的に周期的な$\omega$-wordシーケンスでRNNをトレーニングし、ターゲットBAの振る舞いを再現し、分布外のシーケンスにどのように一般化するかを評価する。 3つの状態から100以上の状態の異なる構造的複雑性の決定論的オートマトンに対応するLTL式の実験を通して、RNNは、トレーニング例より最大8 \times$長いシーケンスで評価された場合、目標の$\omega$-regular言語に対して高い精度を達成でき、そのタスクの92.6\%が完全あるいはほぼ完全な一般化を達成する。 これらの結果は、複雑な$\omega$-regular言語を学ぶためのニューラルネットワークの可能性を確立し、ニューロシンボリック検証手法の構成要素としての可能性を示している。

関連論文リスト

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks [59.85314067235965]
  2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN) 有界時間でチューリング完備な RNN のクラスが存在することを証明している。 また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
  論文  参考訳（メタデータ） (2023-09-26T06:06:47Z)
• Advancing Regular Language Reasoning in Linear Recurrent Neural Networks [56.11830645258106]
  本稿では,リニアリカレントニューラルネットワーク(LRNN)がトレーニングシーケンスに隠された規則を学習できるかを検討する。 ブロック対角および入力依存遷移行列を備えた新しいLRNNを提案する。 実験結果から,提案モデルが正規言語タスクに対して長さ外挿を行うことができる唯一のLRNNであることが示唆された。
  論文  参考訳（メタデータ） (2023-09-14T03:36:01Z)
• Learning Hierarchical Structures with Differentiable Nondeterministic Stacks [25.064819128982556]
  最近提案された非決定論的スタックRNN(NS-RNN)に基づくスタックRNNモデルを提案する。 NS-RNNは,5つの文脈自由言語モデリングタスクにおいて,従来のスタックRNNよりも低エントロピーを実現することを示す。 また,自然言語を用いた言語モデリングを実用化するNS-RNNの限定バージョンを提案する。
  論文  参考訳（メタデータ） (2021-09-05T03:25:23Z)
• SyGNS: A Systematic Generalization Testbed Based on Natural Language Semantics [39.845425535943534]
  自然言語セマンティックス(SyGNS)に基づく体系的一般化テストベッドを提案する。 ニューラルネットワークが、量化子や否定といった論理式の新しい組み合わせを含む文を体系的に解析できるかどうかを検証する。 実験により、Transformer と GRU モデルは、与えられたトレーニングインスタンスの形式に類似しているが、他のモデルには似ていない量化器、否定器、修飾器の組み合わせに一般化できることが示された。
  論文  参考訳（メタデータ） (2021-06-02T11:24:41Z)

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

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