Skip to content

A strengthening of the MCFL-ness of $O_2$

Aug 2026 · 0 citations · 13 references
Computer Science Mathematics

TL;DR

This work focuses on a recent proof of the fact that $O_2$ is a multiple context-free grammar (MCFG) in terms of factorizations of string tuples, and gives a new result with a stronger characterization of such factorizations than in existing theorems.

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.

View source

Similar papers

Preprint Jul 2026

Even smaller universal posets

We show that for every $\eta>0$ and sufficiently large $n$, there exists a poset of size $2^{(1+\eta)n/2}$ containing all the $n$-element posets as induced subposets. This improves a recent result of Bastide, Groenland and Nenadov. Our proof provides a labeling scheme preserving transitivity, inspired by the Boolean lattice. Among other tools, we use the Szemer\'edi Regularity Lemma.

József Balogh, Ramon I. Garcia, M. Sales · 0 citations
Preprint Jul 2026

Splendid extensions

Let $\kappa$ be a successor cardinal. We force a universe in which every model of PA of size $\kappa$ extends to a model M of the same size, where M has no splendid extensions. If there is an ineffable cardinal then this statement holds at some cardinal below it, in ZFC.

S. Garti · 0 citations
Preprint Aug 2026

Failure of Higher-Order Truth within Intuitionistic Propositional Logic

We answer the question whether all Heyting algebras can appear as the lattice of subterminal objects of an elementary topos in the negative. Concretely, we have shown that the free Heyting algebra on two generators cannot be such a Heyting algebra. The mathematical results in this document were obtained with the help of ChatGPT 5.6 Sol, although the document itself was written entirely by us and we take full responsibility for its contents.

Lin Ye, Yi-Qi Xu · 0 citations

A/-TERM REDUCTIONS (

M. D. E. -. Iancaglini, S. Onchi, D. E. R. Occa et al. · 0 citations
Preprint Aug 2026

Positive Lower Density for Hofstadter's $ab-1$ Problem

Let $A$ be the smallest set of positive integers containing $2$ and $3$ such that $ab-1\in A$ whenever $a,b\in A$ are distinct. We prove that $A$ has positive lower density, answering a problem of Erd\H{o}s attributed to Hofstadter.

Samuel Korsky · 0 citations

Related blog posts