Fugu-MT 論文翻訳(概要): VC-dimensions of nondeterministic finite automata for words of equal length

論文の概要: VC-dimensions of nondeterministic finite automata for words of equal length

arxiv url: http://arxiv.org/abs/2001.02309v2
Date: Wed, 4 Aug 2021 18:28:10 GMT
ステータス: 処理完了
システム内更新日: 2023-01-13 21:20:22.556203
Title: VC-dimensions of nondeterministic finite automata for words of equal length
Title（参考訳）: 等しい長さの単語に対する非決定性有限オートマトンのvc次元
Authors: Bj{\o}rn Kjos-Hanssen, Clyde James Felix, Sun Young Kim, Ethan Lamb, Davin Takahashi
Abstract要約: NFA_b(q)$ は、非決定論的有限オートマトンで許容される言語の集合を、$b$文字のアルファベット上の$q$状態とする。 B_n$ は長さ $n$ の単語の集合を表す。
参考スコア（独自算出の注目度）: 2.099922236065961
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_2(q)\cap B_n = \{L\cap B_n \mid L \in NFA_2(q)\} \] as a function of $q$. Next, the work of Gruber and Holzer (2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in $B_n$, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on $n$ of the VC dimension and testing dimension of $NFA_2(q)\cap B_n$.
Abstract（参考訳）: NFA_b(q)$ は、非決定論的有限オートマトンで許容される言語の集合を、$b$文字のアルファベット上の$q$状態とする。 B_n$ は長さ $n$ の単語の集合を表す。 vc次元 \[ nfa_2(q)\cap b_n = \{l\cap b_n \mid l \in nfa_2(q)\} \] の二次下限を$q$の関数として与える。次に gruber と holzer (2007) の仕事は、$b_n$ に含まれる有限言語の非決定論的状態複雑性の上限を与える。最後に、VC次元の$n$とテスト次元の$NFA_2(q)\cap B_n$への依存に関する理論的および実験的結果を示す。

関連論文リスト

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文参考訳（メタデータ） (2024-10-07T19:47:13Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
When Variable-Length Codes Meet the Field of Error Detection [0.0]
citeJK97,N21の精神では、可変長符号の誤り検出補正能力は$tau_d,k$以上の条件で表現できる。所定の正規コードに対して、それらの条件が決定可能であるかどうかを検討する。
論文参考訳（メタデータ） (2022-08-31T08:14:28Z)
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文参考訳（メタデータ） (2022-04-22T12:37:56Z)
Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文参考訳（メタデータ） (2022-02-11T23:53:43Z)
Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
単語のバイナリ関係が与えられたとき、$tau$-Gray サイクルを有限言語 $X$ 上で定義し、置換 $left(w_[i]right)_0le ile |X|-1$ of $X$ とする。アルファベットの基数と引数$n$のすべてのケースに対して有界な$lambda(n)$を計算する。
論文参考訳（メタデータ） (2021-08-31T07:49:15Z)
Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文参考訳（メタデータ） (2021-04-29T14:50:03Z)
Binary strings of finite VC dimension [0.0]
本稿では、P(x+y)$ が有限VC次元を持つような述語 $P$ によって与えられる部分集合について検討する。我々は、有界なVC次元の文字列が実体のトポロジーにおいて意味があることを証明し、文字列のVC次元を境界付けるための単純なルールを提供し、VC次元$d$の二無限文字列が非ソソシフト空間であることを示した。
論文参考訳（メタデータ） (2021-01-16T17:51:52Z)
RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文参考訳（メタデータ） (2020-10-15T04:42:29Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

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