$\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence

• URL: http://arxiv.org/abs/2306.14192v3
• Date: Mon, 11 Sep 2023 06:47:27 GMT
• Title: $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence
• Abstract summary: 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. 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.
• Score: 1.5935205681539144
• 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.

Related papers

• A strengthening of the MCFL-ness of $O_2$ [0.0]
  We prove that $O$ is a multiple context-free grammar (MCFG)<n>We focus on a recent such proof spelled in terms of factorizations of strings, and give a new result with a stronger characterization of such factorizations than in existing theorems.
  arXiv  Detail & Related papers  (2026-08-19T11:11:49Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Cryptographic transformations over polyadic rings [3.0860863056832826]
  cryptosystems rely on binary operations within groups, rings, or fields.<n>We propose a shift to polyadic rings, which generalize classical rings by allowing operations of higher arity.<n>We present two concrete encryption procedures that leverage this structure.
  arXiv  Detail & Related papers  (2025-12-14T07:15:55Z)
• Random Text, Zipf's Law, Critical Length,and Implications for Large Language Models [0.0]
  We study a deliberately simple, fully non-linguistic model of text.<n>A word is defined as a maximal block of non-space symbols.
  arXiv  Detail & Related papers  (2025-11-14T23:05:59Z)
• Causal Estimation of Tokenisation Bias [58.20086589761273]
  We quantify the effect of including or not a subword in a tokeniser's vocabulary on the probability a trained model assigns to the corresponding characters.<n>We find that tokenisation consistently affects models' outputs across scales, vocabularies, and tokenisers.<n> Notably, a subword's presence in a small model's vocabulary may increase its characters' probability by up to 17 times.
  arXiv  Detail & Related papers  (2025-06-03T17:59:47Z)
• CoKe: Customizable Fine-Grained Story Evaluation via Chain-of-Keyword Rationalization [90.15027447565427]
  Chain of thought (CoT) generates free-text explanations that help guide a model's predictions.<n>Self-Consistency (SC) marginalizes predictions over multiple generated explanations.<n>We propose $textbfC$hain-$textbfo$f-$textbfKe$ywords (CoKe)
  arXiv  Detail & Related papers  (2025-03-21T13:37:46Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder. We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• The Magnitude of Categories of Texts Enriched by Language Models [1.8416014644193064]
  We use the next-token probabilities given by a language model to define a $[0,1]$-enrichment of a category of texts in natural language. We compute the M"obius function and the magnitude of an associated generalized space $mathcalM$ of texts.
  arXiv  Detail & Related papers  (2025-01-11T23:28:50Z)
• Interchangeable Token Embeddings for Extendable Vocabulary and Alpha-Equivalence [6.991281327290525]
  We propose a novel approach for learning interchangeable tokens in language models. Our method addresses alpha-equivalence, the principle that renaming bound variables preserves semantics. Our method demonstrates promising generalization capabilities as well as a favorable inductive bias for alpha-equivalence.
  arXiv  Detail & Related papers  (2024-10-22T16:34:36Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
  Universal hash functions map the output of a source to random strings over a finite alphabet. We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
  arXiv  Detail & Related papers  (2024-10-21T19:37:35Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  We introduce the notion of a margin complement, which measures how much a prediction score $S$ changes due to a thresholding operation. We show that under suitable causal assumptions, the influences of $X$ on the prediction score $S$ are equal to the influences of $X$ on the true outcome $Y$.
  arXiv  Detail & Related papers  (2024-05-24T11:22:19Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Signal in Noise: Exploring Meaning Encoded in Random Character Sequences with Character-Aware Language Models [0.7454831343436739]
  We show that $n$-grams composed of random character sequences, or $garble$, provide a novel context for studying word meaning within and beyond extant language. By studying the embeddings of a large corpus of garble, extant language, and pseudowords using CharacterBERT, we identify an axis in the model's high-dimensional embedding space that separates these classes of $n$-grams.
  arXiv  Detail & Related papers  (2022-03-15T13:48:38Z)
• m-Nearly k-Universal Words -- Investigating Simon Congruence [1.3229510087215552]
  Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors. We show some results if in addition $w$ is $(k-1)$-universal as well as some further insights for different $m$.
  arXiv  Detail & Related papers  (2022-02-16T10:45:10Z)
• Clustering and Network Analysis for the Embedding Spaces of Sentences and Sub-Sentences [69.3939291118954]
  This paper reports research on a set of comprehensive clustering and network analyses targeting sentence and sub-sentence embedding spaces. Results show that one method generates the most clusterable embeddings. In general, the embeddings of span sub-sentences have better clustering properties than the original sentences.
  arXiv  Detail & Related papers  (2021-10-02T00:47:35Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Scattered Factor Universality -- The Power of the Remainder [1.8065361710947976]
  Scattered factor (circular) was firstly introduced by Barker et al. in 2020. We prove two problems, namely a generalisation of one of their main theorems to arbitrary alphabets and a slight modification of another theorem.
  arXiv  Detail & Related papers  (2021-04-19T05:45:44Z)
• Superposition with Lambdas [59.87497175616048]
  We design a superposition calculus for a clausal fragment of extensional polymorphic higher-order logic that includes anonymous functions but excludes Booleans. The inference rules work on $betaeta$-equivalence classes of $lambda$-terms and rely on higher-order unification to achieve refutational completeness.
  arXiv  Detail & Related papers  (2021-01-31T13:53:17Z)
• Learning Languages with Decidable Hypotheses [1.2728819383164875]
  In language learning in the limit, the most common type of hypothesis is to give an enumerator for a language. This so-called $W$-index allows for naming arbitrary computably enumerable languages. We use a different system which allows for naming arbitrary decidable languages, namely programs for characteristic functions (called $C$-indices)
  arXiv  Detail & Related papers  (2020-10-15T09:27:47Z)
• Principal Word Vectors [5.64434321651888]
  We generalize principal component analysis for embedding words into a vector space. We show that the spread and the discriminability of the principal word vectors are higher than that of other word embedding methods.
  arXiv  Detail & Related papers  (2020-07-09T08:29:57Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. We show that both variants attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively. In a contextual setting, we show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
  arXiv  Detail & Related papers  (2020-07-07T09:00:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.