論文の概要: On the Power of Unambiguity in B\"uchi Complementation

• arxiv url: http://arxiv.org/abs/2005.09125v2
• Date: Wed, 23 Sep 2020 01:27:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-02 00:08:07.288661
• Title: On the Power of Unambiguity in B\"uchi Complementation
• Title（参考訳）: B\「内補足」における曖昧さの力について
• Authors: Yong Li (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences), Moshe Y. Vardi (Rice University), Lijun Zhang (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences)
• Abstract要約: 我々は,B"uchi Automaticaの補間問題に対して,不明瞭さの力を利用する。 我々は,このタイプの縮小型DAGを,ランクベースおよびスライスベース補完構造を最適化するインフン化ツールとして利用する方法を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we exploit the power of \emph{unambiguity} for the complementation problem of B\"uchi automata by utilizing reduced run directed acyclic graphs (DAGs) over infinite words, in which each vertex has at most one predecessor. We then show how to use this type of reduced run DAGs as a \emph{unified tool} to optimize \emph{both} rank-based and slice-based complementation constructions for B\"uchi automata with a finite degree of ambiguity. As a result, given a B\"uchi automaton with $n$ states and a finite degree of ambiguity, the number of states in the complementary B\"uchi automaton constructed by the classical rank-based and slice-based complementation constructions can be improved, respectively, to $2^{O(n)}$ from $2^{O(n\log n)}$ and to $O(4^n)$ from $O((3n)^n)$.
• Abstract（参考訳）: 本研究では,B\"uchi Automatica の補数問題に対する 'emph{unambiguity} のパワーを,各頂点が少なくとも1つの前駆体を持つ無限語上の簡約有向非巡回グラフ (DAG) を利用して活用する。 次に、B\"uchi Automatica のランクベースおよびスライスベース補完構造を有限のあいまいさで最適化するために、このような縮小実行 DAG を \emph{Unified tool} として利用する方法を示す。 その結果、n$状態と有限な曖昧度を持つb\"uchiオートマトンが与えられると、古典的なランクベースとスライスベースの補完構造によって構築された補完的b\"uchiオートマトンにおける状態の数は、それぞれ$2^{o(n\log n)}$から$2^{o(n\log n)}$から$o(4^n)$から$o(3n)^n)$に改善される。

関連論文リスト

• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training [31.08452714165316]
  2つの集合 $A の部分集合 -1,+1d$ と $B の部分集合 -1,+1d$ と $|A|=|B| = n$ が与えられる。 我々は$O(n2 omega / 3+ o(1))$時間で、$rhoを超える$k$内部積ペアを見つけるアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-11-19T21:40:16Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis [36.646876613637325]
  マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T08:18:47Z)
• On the Intersection of Context-Free and Regular Languages [71.61206349427509]
  我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。 我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
  論文  参考訳（メタデータ） (2022-09-14T17:49:06Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error [18.19398247972205]
  我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。 UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-08T03:22:39Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Optimal Strategies for Graph-Structured Bandits [0.0]
  Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
  論文  参考訳（メタデータ） (2020-07-07T06:27:51Z)

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

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