Why Are Linear RNNs More Parallelizable?
この論文は、線形 RNN が非線形 RNN と異なりトランスフォーマーと同様に並列化可能である理由を、線形 RNN が対数深さの算術回路（ 等）として記述できるのに対し、非線形 RNN は並列化の根本的な障壁となる P 完全問題などを解き得るという計算複雑性理論の観点から解明し、表現力と並列性の最適なバランスを設計するための基礎を提供しています。
💻 Category
cs.FL
28 件の論文
2-Coloring Cycles in One Round
この論文は、大規模言語モデルによって発見・開発され Lean 4 で形式化された、1 ラウンドのランダム化分散アルゴリズムを用いたサイクルの 2 彩色において、単色辺の期待割合が 0.24118 未満となる上限と 0.23879 未満にはなり得ない下限をそれぞれ示すものである。
Reachability in VASS Extended with Integer Counters
本論文は、非負制約を持つ N カウンターと整数制約のない Z カウンターを備えた VASS（VASS+Z）の到達可能性問題の複雑性を研究し、N カウンターが 1 つの場合は NP 完全であることを示すとともに、N カウンターが 2 つ以上の場合の上限を改善し、Z カウンターの導入によって高次元 VASS における PSPACE 困難性や TOWER 困難性がより低い次元で達成されることを証明したものである。
Algebraic Characterization of Reversible First Degree Cellular Automata over
この論文は、任意のセル数を持つ有限一次元セルオートマトンの可逆性を定数時間で判定し、すべての可逆ルールを合成するための、パラメータ値に関する 3 つの代数的条件を導出する手法を提案しています。
Computational Complexity of Alignments
この論文は、プロセスマイニングにおけるアライメント計算の計算量複雑性を調査し、安全な Petri ネットやワークフローネットでは PSPACE 完全である一方、ライブかつ有界な自由選択システムでは NP に位置し、さらにライブかつ安全な S システムでは多項式時間で解けることを示しています。
History-Deterministic Büchi Automata are Succinct
本論文は、歴史決定性 Büchi オートマトンが言語等価な決定性 Büchi オートマトンよりも厳密に少ない状態数で表現可能であることを示し、10 年以上にわたり未解決だった問題に、理論的洞察とコンピュータ支援を組み合わせた 65 状態の具体例によって決着をつけた。
Formal Analysis of the Contract Automata Runtime Environment with Uppaal: Modelling, Verification and Testing
本論文は、Uppaal による確率的時間オートマトンの形式モデル化、検証、および抽象テストの具体化を通じて、分散ミドルウェア「CARE」の信頼性向上を可能にする手法を提示しています。
SpotIt: Evaluating Text-to-SQL Evaluation with Formal Verification
本論文は、既存のテストベースの評価手法が見落としがちな生成 SQL と正解 SQL の差異を特定するために、形式検証エンジンを用いて両者を区別するデータベースを探索する新たな評価パイプライン「SpotIt」を提案し、BIRD データセットを用いた実験によりその有効性を示しています。