論文の概要: $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence
- arxiv url: http://arxiv.org/abs/2306.14192v1
- Date: Sun, 25 Jun 2023 10:16:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 16:11:19.528316
- Title: $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence
- Title（参考訳）: $\alpha$-$\beta$-Factorization と Simon's Congruence のバイナリケース
- Authors: Pamela Fleischmann, Jonas H\"ofer, Annika Huch, Dirk Nowotka
- Abstract要約: 1991年、H'ebrardは単語の因数分解を導入し、単語の散らばった要因を調べる強力なツールとなった。
これに基づいて、最初のカランディカールとシュネーベレンは$k$-richness(英語版)という概念を導入し、後にBarkerらに$k$-universality(英語版)という概念を導入した。
2022年、フライシュマンらは、単語のアーチ因数分解とその逆を交差させることにより、アーチ因数分解の一般化を提示した。
- 参考スコア（独自算出の注目度）: 1.4452289368758382
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In 1991 H\'ebrard introduced a factorization of words that turned out to be a
powerful tool for the investigation of a word's scattered factors (also known
as (scattered) subwords or subsequences). Based on this, first Karandikar and
Schnoebelen introduced the notion of $k$-richness and later on Barker et al.
the notion of $k$-universality. In 2022 Fleischmann et al. presented a
generalization of the arch factorization by intersecting the arch factorization
of a word and its reverse. While the authors merely used this factorization for
the investigation of shortest absent scattered factors, in this work we
investigate this new $\alpha$-$\beta$-factorization as such. We characterize
the famous Simon congruence of $k$-universal words in terms of $1$-universal
words. Moreover, we apply these results to binary words. In this special case,
we obtain a full characterization of the classes and calculate the index of the
congruence. Lastly, we start investigating the ternary case, present a full
list of possibilities for $\alpha\beta\alpha$-factors, and characterize their
congruence.
- Abstract（参考訳）: 1991年、H'ebrardは単語の因数分解を導入し、単語の散在する要素(散在した)や部分列(サブワード)を調べる強力なツールとなった。
これに基づいて、最初のカランディカールとシュネーベレンは$k$-richnessという概念を導入し、後にBarkerらに$k$-universalityという概念を導入した。
2022年、fleischmannらは、単語とその逆のアーチ分解を交差させることで、アーチ分解の一般化を示した。
著者らは, この因子分解を, 最短欠落因子の探索にのみ用いたが, 本研究では, 新規な$\alpha$-$\beta$-factorization について検討する。
我々は、有名なsimon congruenceのk$universalワードを1$universalワードで特徴づける。
さらに,これらの結果をバイナリ単語に適用する。
この特別な場合、クラスを完全に特徴づけ、合同の指標を計算する。
最後に、三項ケースの調査を開始し、$\alpha\beta\alpha$-factorsの完全なリストを示し、それらの一貫性を特徴づける。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Signal in Noise: Exploring Meaning Encoded in Random Character Sequences
with Character-Aware Language Models [0.7454831343436739]
ランダムな文字列からなる$n$-grams、または$garble$は、現在ある言語内外における単語の意味を研究するための新しい文脈を提供する。
characterBERT を用いて,巨大コーパス,既存言語,擬似単語の埋め込みを研究することにより,モデルの高次元埋め込み空間の軸を同定し,これらのクラスを$n$-gram で分離する。
論文 参考訳（メタデータ） (2022-03-15T13:48:38Z) - m-Nearly k-Universal Words -- Investigating Simon Congruence [1.3229510087215552]
2つの単語 $u$ と $v$ は、それらが同じ散乱因子の集合を持つ場合、サイモン合同 (Simon congruent) と呼ばれる。
さらに、$w$が$(k-1)$-ユニバーサルであれば、いくつかの結果が得られます。
論文 参考訳（メタデータ） (2022-02-16T10:45:10Z) - Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。
主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。
2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
論文 参考訳（メタデータ） (2021-07-14T07:23:46Z) - Scattered Factor Universality -- The Power of the Remainder [1.8065361710947976]
Scattered Factor (circular) はBarkerらによって最初に導入された。
2020年。
2つの問題、すなわち、主定理の1つを任意のアルファベットに一般化し、他の定理をわずかに修正したことを証明する。
論文 参考訳（メタデータ） (2021-04-19T05:45:44Z) - Superposition with Lambdas [59.87497175616048]
匿名関数を含むがブール関数を除いた拡張多型高階論理のクラスフラグメントに対する重ね合わせ計算を設計する。
推論ルールは$betaeta$-equivalence class of $lambda$-termsで動作し、難解な完全性を達成するために高階統一に依存する。
論文 参考訳（メタデータ） (2021-01-31T13:53:17Z) - Learning Languages with Decidable Hypotheses [1.2728819383164875]
極限における言語学習において、最も一般的な仮説は、ある言語の列挙子を与えることである。
いわゆる$W$-indexは任意の計算可能可算言語を命名することができる。
我々は、任意の決定可能な言語、すなわち特徴関数のプログラムを命名できる別のシステム($C$-indices)を使用している。
論文 参考訳（メタデータ） (2020-10-15T09:27:47Z) - Principal Word Vectors [5.64434321651888]
単語をベクトル空間に埋め込むための主成分分析を一般化する。
主語ベクトルの拡散と識別性は他の単語埋め込み法よりも高いことを示す。
論文 参考訳（メタデータ） (2020-07-09T08:29:57Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。