A strengthening of the MCFL-ness of $O_2$

Marco B. Caminati

cs.FLAug 19, 2026

A strengthening of the MCFL-ness of $O_2$

Authors: Marco B. Caminati

Organizations: Lancaster University, Leipzig, Germany

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.

Figures & tables

Figure 1: Three applications of Lemma 1 to the case

x_{0}=1

y_{0}=1

x_{2}=4

y_{1}=6

x_{1}=5

x_{3}=1

Panel of Figure 2 — Figure 2: Configurations of a minimal bump $\left[i,j\right]\in B^{b}\left(p_{0},p_{1}\right)$ . $p_{0}$ goes from the circle (the origin) to the square ( $\mu\left(p_{0}\right)$ ), while $p_{1}$ goes from the square to the circle.

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
May 12, 2026Takayuki Kuriyama
Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation
Sep 3, 2026Takayuki Kuriyama
Independent Researcher, Tokyo, Japan
Putnam 2025 Problems in Rocq using Opus 4.6 and Rocq-MCP
Mar 20, 2026Guillaume Baudart, Marc Lelarge, Tristan Stérin +1Large Language Model-Guided Theorem Proving Automated Theorem Proving
IRIF, Université Paris Cité, Inria, CNRS · DI ENS, PSL University, Inria · PRGM DEV

May 12, 2026J/K move · Enter open · S save

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing

Takayuki Kuriyama

Open paper AskPDF arXiv

We study positive-data learning of bounded-fan-out linear multiple context-free grammars under a fixed explicit finite monoid homomorphism

h

. The main obstacle beyond the context-free case is that an MCFG nonterminal derives a tuple whose components may be placed in a surrounding sentence in different orders. We introduce sentence-interface types as finite external control objects for such tuple occurrences. A type records the permutation of tuple components in the final sentence together with the

h

-values of the boundary intervals between them. For reduced working binary linear nondeleting MCFG presentations whose string languages satisfy

(f,h)

-tuple substitutability, we build a typed refinement, a finite characteristic sample, and a canonical positive-data learner. Once the sample contains this characteristic sample and remains contained in the target language, the learner reconstructs the language exactly. Consequently, for fixed fan-out bound

f

and fixed explicit

h

, the resulting class is identifiable in the limit from positive data. Moreover, the hypothesis associated with any given finite sample is constructible in polynomial time for fixed

f

and fixed

h

, including output size. Thus sentence-interface control is the finite mechanism that lifts fixed-

h

distributional reconstruction from context-free grammars to bounded-fan-out linear MCFGs.

Abstract

Explore similar work

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation

Putnam 2025 Problems in Rocq using Opus 4.6 and Rocq-MCP