CS Paper Radar

On the Kanazawa--Salvati Conjecture

Takao Yuyama

cs.FL ·submitted 2026-09-12 10:48 UTC · v1
theory

Abstract

The language $\mathrm{MIX}$ consists of all words over a three-letter alphabet that have an equal number of occurrences of each letter. It is also the word problem of $\mathbb{Z}^2$ with respect to a suitable choice of generators. The Kanazawa--Salvati conjecture states that $\mathrm{MIX}$ is not a well-nested multiple context-free language. Every well-nested multiple context-free language is an indexed language. We reduce the conjecture to an explicit combinatorial problem about tuples of words, which is easier to state than the original formulation in terms of arbitrary well-nested multiple context-free grammars. More generally, for every surjective monoid homomorphism $ψ\colon Σ^* \to \mathbb{Z}^d$, we define a family of well-nested multiple context-free grammars $G_ψ[r]$ for $r \geq 1$, each of which generates a sublanguage of $ψ^{-1}(\mathbf{0})$. We prove that every well-nested multiple context-free sublanguage of $ψ^{-1}(\mathbf{0})$ is contained in $L(G_ψ[r])$ for some $r \geq 1$. Using this family, we prove that the four-letter analogue $\mathrm{MIX}_4$, which is a word problem of $\mathbb{Z}^3$, is not a well-nested multiple context-free language. The proof reduces this claim to a result of Bishop--Elder--Evetts--Gallot--Levine stating that the two-letter analogue $\mathrm{MIX}_2$ is not generated by any non-branching multiple context-free grammar. The Kanazawa--Salvati conjecture itself remains open.

Comment
39 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A strengthening of the MCFL-ness of $O_2$

cs.FL cs.AIcs.LOmath.LO ·2026-08-19 ·Marco B. Caminati
similarity 0.67
Abstract · MCU 2026

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.

0.24

Non-Terminal Complexity of Simple Semi-Conditional Grammars

cs.FL math.LO ·2026-09-12 ·Henning Fernau, Sanjay Jain, Linus Richter, Frank Stephan, Dan Turetsky
theory similarity 0.59
Abstract · 26 pages

We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.

0.16

Conjugacy languages in free inverse monoids

cs.FL math.GR ·2026-08-11 ·André Carvalho, Ana-Catarina C. Monteiro
similarity 0.59
Abstract · preliminary version, 24 pages

We initiate the study of conjugacy languages in free inverse monoids. Motivated by the notion of conjugacy languages in groups and the study of conjugacy in semigroups, we introduce the language of shortest representatives of conjugacy classes and study it for free inverse monoids of rank at least $2$ under the natural notion of conjugacy. We show that, contrary to the free group case, where this language is regular, in a free inverse monoid it is neither context-free nor co-context-free. In the monogenic case, this language is context-free. We show that this non-context-freeness comes from elements with nontrivial conjugacy classes. We define an equivalence relation as follows: all elements with a nontrivial conjugacy class are related and elements with trivial conjugacy class are only related to themselves. We call this relation $\mathrm{UConj}$. We show that the language consisting of geodesics representing elements whose conjugacy class is trivial is context-free by providing an explicit context-free grammar generating it. For groups, we show that the language of minimal representatives of $\mathrm{UConj}$ classes is regular if the group is hyperbolic and for right-angled Artin groups with the standard generating set, it is piecewise testable. For virtually abelian groups, we show that there is a generating set for which this language is piecewise excluding and exhibit an example of a virtually abelian group admitting a generating set for which this language is not regular.

0.10

Contributions to the hierarchy of probabilistic languages

cs.FL cs.CLmath.LOmath.PR ·2026-09-20 ·Lothar Sebastian Krapp, Remo Nitschke
similarity 0.57
Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

0.46

On the equivalence between generating functions computed by memory transducers and enumerating functions produced by indexed grammars

cs.FL ·2026-09-04 ·Vincent Ghigo
theory similarity 0.57
Abstract

We consider the sequences of natural integers that can be computed by a deterministic transducer, with input in a structure A, output in N. and with memory the set of stacks of stacks of A. We show that these sequences are, exactly, the counting sequences of formal languages generated by unambiguous context-free indexed grammars (equivalently, the counting sequences of derivation trees of arbitrary context-free indexed grammars), with indexes in A. This general theorem applies, notably, to the set of natural integers endowed with the operation -1 and the non-zero predicate, showing that the polynomial recurrences count exactly the index-languages (where the parameter used for counting is the index itself).

0.25

Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy

cs.FL math.GR ·2026-08-30 ·Takayuki Kuriyama
similarity 0.57
Abstract · 43 pages, 2 tables

Clark's syntactic concept lattice (SCL) records two-sided distributional structure, and Wurm extended it to tuples of arbitrary finite arity. We study \(\operatorname{cmp}_f(L)\), the minimum image size of a finite-monoid observation that preserves guarded tuple substitution through arity \(f\) on the principal layer. For regular languages, we characterize \(\operatorname{cmp}_f(L)\) exactly as the least cardinality of the codomain of an \(f\)-separating relational morphism from the pointed syntactic monoid. Let \(\operatorname{ch}(\mathbf V)\) denote the least arity at which these compression numbers stabilize uniformly over a pseudovariety \(\mathbf V\). Our main result is the following trichotomy of possible uniform heights: \(\operatorname{ch}(\mathbf V)\in\{1,2,\infty\}\), with \(\operatorname{ch}(\mathbf V)=\infty\) if and only if \(\operatorname{Synt}(\{ab\})\in\mathbf V\). Thus no finite uniform compression height \(3,4,\ldots\) occurs. The infinite case is sharp: inside \(\langle\operatorname{Synt}(\{ab\})\rangle\), every boundary \(d\to d+1\) admits unbounded compression gaps, and arbitrary finite strict prefixes of the arity hierarchy are realizable. On the finite side, commutative monoids and bands stabilize at arity one, while every completely regular syntactic monoid stabilizes by arity two; finite group kernels show that the binary bound is sharp. At unary arity, every nonempty finite simple graph is realized by an explicit length-three language, yielding an exact chromatic-number formula and NP-completeness of deciding \(\operatorname{cmp}_1(L)\le 3\) for explicitly listed length-three languages. The structural boundary between compression heights one and two remains open.

0.31

Formal Grammars and Generating Functions: From Algebraic Structure to Non-Algebraic and Non-Derivable Series

cs.FL ·2026-10-22 ·Zhijun Wang
theory similarity 0.56
Abstract

This paper investigates how the algebraic and analytic properties of ordinary length generating functions constrain the grammatical and computational complexity of formal languages. We review the Chomsky-Schutzenberger representation, DSV translations for unambiguous context-free grammars, and their stack-indexed extensions, distinguishing finite algebraic systems from more general constructions. Examples and a diagonal argument demonstrate that even a rational generating function need not determine a language's grammatical class. Our central computability result establishes that, for a recursively enumerable language, computability of its length-counting sequence is equivalent to decidability of membership. Consequently, if a recursively enumerable language has a D-finite length generating function over Q(z), it is decidable; equivalently, undecidable recursively enumerable languages cannot have D-finite length generating functions. We then examine coefficient growth and singularities through Pringsheim's theorem, the Polya-Carlson dichotomy, Hadamard gaps, and Siegel G-functions. The resulting picture is asymmetric: analytic properties provide useful one-way constraints on language computability, but length enumeration loses too much information to determine grammatical or computational complexity without additional assumptions.

0.12

The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence

cs.FL cs.CLcs.LO ·2026-11-01 ·Sherzod Turaev
similarity 0.56
Abstract · 13 pages, 1 figure, 1 table

A rule written for people fixes its atomic conditions and connectives but leaves open how the connectives are bracketed, and each bracketing is a different logical reading that an autoformalizer must resolve or expose. We study the scope grammar, a deliberately ambiguous context-free grammar whose derivation trees are the readings of a connective skeleton and whose quotient by logical equivalence is what matters downstream. A skeleton with $k$ binary connectives has $C_k$ derivation trees, the $k$-th Catalan number, but far fewer logically distinct readings. For the positive, repetition-free fragment we make the gap exact: through the uniqueness of the read-once normal form we characterize the realizable normal forms by lowest common ancestors and count them with a two-label recurrence over the operator word, verified against exhaustive enumeration up to eleven atoms. The count is invariant under reversal and $\wedge/\vee$ duality; a skeleton is ambiguous if and only if it uses both $\wedge$ and $\vee$, a one-pass test; and the number of classes is at least $2^{\lfloor n/3\rfloor}$. Up to fifteen atoms the alternating pattern is the worst case; its count has a cubic generating function, is the 3-Schröder sequence (OEIS A137842), and grows with base $\varphi^{5/2}\approx3.330$, below the Catalan base 4. We reduce maximality to an inequality on increments, verified to sixteen atoms, and explain why local exchange arguments cannot prove it. We also treat negation, exceptions, and background axioms, where normal-form uniqueness still decides equivalence but counting is open.

0.28