A strengthening of the MCFL-ness of $O_2$

• URL: http://arxiv.org/abs/2608.18813v1
• Date: Wed, 19 Aug 2026 11:11:49 GMT
• Title: A strengthening of the MCFL-ness of $O_2$
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.

Related papers

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems.<n>We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• $O_2$ is a multiple context-free grammar: an implementation-, formalisation-friendly proof [0.0]
  Classifying languages according to the expressiveness of grammars able to generate them is a fundamental problem in computational linguistics. This paper analyses the existing proofs from the computational and the proof-theoretical point of views systematically studying whether each proof can lead to a verified (i.e., checked by a proof assistant) algorithm parsing balanced languages via MCFGs.
  arXiv  Detail & Related papers  (2024-05-15T14:51:11Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence [1.5935205681539144]
  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.
  arXiv  Detail & Related papers  (2023-06-25T10:16:49Z)
• An Operator Splitting View of Federated Learning [15.968575321322225]
  In the past few years, the learning ($texttFL$) community has witnessed a proliferation of new $texttFL$ algorithms.<n>We compare different algorithms with ease, to previous convergence results and to uncover new algorithmic variants.<n>The unification algorithms also leads a way to accelerate $texttFL$ algorithms, without any overhead.
  arXiv  Detail & Related papers  (2021-08-12T21:22:06Z)
• Proof-theoretic aspects of NL$\lambda$ [0.0]
  We present a proof-theoretic analysis of the logic NL$lambda$. We introduce a novel calculus of proof nets and prove it is sound and complete with respect to the sequent calculus for the logic. We show there is an unexpected convergence of the natural language analyses proposed in the two formalisms.
  arXiv  Detail & Related papers  (2020-10-23T08:13:39Z)
• The Return of Lexical Dependencies: Neural Lexicalized PCFGs [103.41187595153652]
  We present novel neural models of lexicalized PCFGs which allow us to overcome sparsity problems. Experiments demonstrate that this unified framework results in stronger results on both representations than achieved when either formalism alone.
  arXiv  Detail & Related papers  (2020-07-29T22:12:49Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• MIP*=RE [9.42581332803306]
  We show that the class MIP* of languages can be decided by a classical verifier interacting with multiple quantum provers sharing entanglement. We provide a refutation of Connes' theory of von Neumann algebras.
  arXiv  Detail & Related papers  (2020-01-13T16:32:40Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.