論文の概要: Binary strings of finite VC dimension

• arxiv url: http://arxiv.org/abs/2101.06490v2
• Date: Sun, 24 Jan 2021 14:00:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-28 04:30:01.552335
• Title: Binary strings of finite VC dimension
• Title（参考訳）: 有限vc次元のバイナリ文字列
• Authors: Hunter R Johnson
• Abstract要約: 本稿では、P(x+y)$ が有限VC次元を持つような述語 $P$ によって与えられる部分集合について検討する。 我々は、有界なVC次元の文字列が実体のトポロジーにおいて意味があることを証明し、文字列のVC次元を境界付けるための単純なルールを提供し、VC次元$d$の二無限文字列が非ソソシフト空間であることを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Any binary string can be associated with a unary predicate $P$ on $\mathbb{N}$. In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. This provides a measure of complexity for binary strings with different properties than the standard string complexity function (based on diversity of substrings). We prove that strings of bounded VC dimension are meagre in the topology of the reals, provide simple rules for bounding the VC dimension of a string, and show that the bi-infinite strings of VC dimension $d$ are a non-sofic shift space. Additionally we characterize the irreducible strings of low VC dimension (0,1 and 2), and provide connections to mathematical logic.
• Abstract（参考訳）: 任意のバイナリ文字列は、unarypredicate $p$ on $\mathbb{n}$と関連付けることができる。 本稿では、P(x+y)$ が有限VC次元を持つような述語 $P$ によって与えられる部分集合について検討する。 これは、標準的な文字列複雑性関数(サブストリングの多様性に基づく)とは異なる性質を持つバイナリ文字列に対する複雑性の尺度を提供する。 我々は、有界なvc次元の文字列が実数体のトポロジーにおいて単純であることを証明し、文字列のvc次元を束縛するための簡単な規則を提供し、vc次元 $d$ の無限の文字列が非実数シフト空間であることを示す。 さらに、低VC次元(0,1,2)の既約文字列を特徴づけ、数学的論理と接続する。

関連論文リスト

• CSPs with Few Alien Constraints [12.330326247154968]
  CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。 我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
  論文  参考訳（メタデータ） (2024-08-23T08:34:13Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Generalization Properties of Decision Trees on Real-valued and Categorical Features [2.370481325034443]
  データ分割の観点から二分決定木を再検討する。 我々は3種類の特徴を考察する: 実数値、分類的順序、分類的名目で、それぞれ異なる分割規則を持つ。
  論文  参考訳（メタデータ） (2022-10-18T21:50:24Z)
• 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)
• 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)
• Understanding and Compressing Music with Maximal Transformable Patterns [0.0]
  点集合の最大パターンを探索するアルゴリズム、$DinmathbbRk$を提案する。 また、これらの最大パターンのそれぞれに対して発生の集合を探索する第2のアルゴリズムを提案する。 民謡旋律を調律語族に分類する作業において,3種類の異なる複雑性のクラスで新しい圧縮アルゴリズムを評価する。
  論文  参考訳（メタデータ） (2022-01-26T17:47:26Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
  2つの平行な均質層からなる構造は、その幅が$l_j$と$l_j$であり、それらの間の距離が$r$を同時に0に縮めるように、極限において研究される。 非自明な有界状態の存在は、ディラックのデルタ関数の微分の形で圧縮ポテンシャルの特別な例を含む、スクイーズ極限で証明される。 有限系の有限個の有界状態から、一個の有界状態が圧縮された系で生き残るシナリオを詳述する。
  論文  参考訳（メタデータ） (2020-11-23T14:40:27Z)
• Invariant subspaces of two-qubit quantum gates and their application in the verification of quantum computers [0.0]
  我々は、$CP$、$CNOT$および$SWAPalpha$(SWAPのパワー)量子ゲート演算が$n$量子ビットに作用する群について検討する。 各群の作用の下で、$n-$qubit ヒルベルト空間の不変部分空間を決定することができる。
  論文  参考訳（メタデータ） (2020-09-08T11:22:43Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。 例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
  論文  参考訳（メタデータ） (2020-08-06T09:50:29Z)
• VC-dimensions of nondeterministic finite automata for words of equal length [2.099922236065961]
  NFA_b(q)$ は、非決定論的有限オートマトンで許容される言語の集合を、$b$文字のアルファベット上の$q$状態とする。 B_n$ は長さ $n$ の単語の集合を表す。
  論文  参考訳（メタデータ） (2020-01-07T22:49:55Z)

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

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