論文の概要: 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$への依存に関する理論的および実験的結果を示す。
関連論文リスト
- 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) - Matrix hypercontractivity, streaming algorithms and LDCs: the large
alphabet case [5.88864611435337]
大型アルファベット上で定義される行列値関数に対する超収縮的不等式を証明した。
逆数モデルの全てのストリーミングアルゴリズムが$(r-varepsilon)$-approximationを達成するためには、$Omega(n1-2/t)$量子空間が必要である。
論文 参考訳(メタデータ) (2021-09-06T16:56:19Z) - 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) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。