Commutative regularity of Kleene closures of bounded semi-linear languages: extending Carpi–D'Alessandro's Theorem 1 beyond codes and the two-distinct-letters condition

Two words are commutatively equivalent when one is obtained from the other by permuting its letters, and two languages are commutatively equivalent when a bijection between them preserves this relation. Carpi and D'Alessandro (Theoret. Comput. Sci. 852, 2021) proved that if L is a bounded semi-linear language that is a uniquely decipherable code and every generator word of a semi-linear representation of L contains at least two distinct letters, then L is commutatively equivalent to an effectively constructible regular code L', so the Kleene closure L* is commutatively equivalent to the regular language (L')*. Their concluding remarks (Section 5) propose as the natural continuation to extend Theorem 1 by dropping the two-distinct-letters condition or by relaxing the code hypothesis, and their final paragraph states that the study of the conditions guaranteeing that a monoid generated by a bounded semi-linear language is commutatively regular appears as a natural issue. The open problem is this extension: is the Kleene closure of a bounded semi-linear language still commutatively equivalent to a regular language when either hypothesis of Theorem 1 is removed, and, in the unconditional form of the general issue posed at the end of Section 5, is the Kleene closure of every bounded semi-linear language commutatively equivalent to a regular language? The problem remains open.

Background

A language is a set of finite words over a finite alphabet $A$ ; it is regular if it is accepted by a finite automaton and context-free if it is generated by a context-free grammar. Two words are commutatively equivalent if one is a permutation (rearrangement of letters) of the other; two languages $L_1, L_2$ are commutatively equivalent if there is a bijection $f : L_1 \to L_2$ such that each $u \in L_1$ is commutatively equivalent to $f(u)$ . A language commutatively equivalent to a regular one is called commutatively regular. The study of this notion is motivated in part by the theory of (variable-length) codes: a language $L$ is a code (uniquely decipherable) if every word of $L^*$ has at most one factorization over $L$ , and the celebrated Schützenberger conjecture asks whether every maximal finite code is commutatively equivalent to a prefix code.

The central question of this line of research is the CE Problem: given a context-free language $L_1$ , does there exist a regular language $L_2$ commutatively equivalent to $L_1$ ? The answer cannot always be positive. For a language $L$ , define its commutative generating series (Parikh series) as the multivariate series $\sum_{w \in L} \mathbf{x}^{\psi(w)}$ in commuting variables $\mathbf{x} = (x_a)_{a \in A}$ , where the Parikh map $\psi$ records each letter's number of occurrences in a word, so that the coefficient of a monomial $\mathbf{x}^{\mathbf{n}}$ counts the words of $L$ with letter-content $\mathbf{n}$ . Commutatively equivalent languages have equal commutative generating series, the commutative series of a regular language is always rational (a componentwise quotient of polynomials), while there exist context-free languages, even unambiguous linear ones, whose commutative generating series are not rational (Flajolet). A basic dichotomy constrains the problem: the growth function $g_L(n)$ , counting words of $L$ of length at most $n$ , makes every context-free language either sparse (polynomially bounded growth) or of exponential growth; moreover the sparse context-free languages are exactly the bounded context-free languages, where a language $L$ is bounded if $L \subseteq u_1^* \cdots u_k^*$ for some finite list of words $u_1, \dots, u_k$ .

Bounded context-free languages were structurally characterized by Ginsburg and Spanier through semi-linear sets. A subset of $\mathbb{N}^k$ is semi-linear if it is a finite union of linear sets, each of the form $B_i = \{b_{i0} + x_1 b_{i1} + \cdots + x_{m_i} b_{i m_i} \mid x_j \in \mathbb{N}\}$ with integer vectors $b_{i0}$ (the base) and $b_{i1}, \dots, b_{i m_i}$ (the periods). The words of $u_1^* \cdots u_k^*$ are encoded by their exponent vectors through the Ginsburg map $\varphi(\ell_1, \dots, \ell_k) = u_1^{\ell_1} \cdots u_k^{\ell_k}$ , and the Ginsburg–Spanier theorem states that a bounded language $L$ is context-free if and only if $\varphi^{-1}(L)$ is a finite union of linear sets each having a stratified set of periods — informally, a system of well-formed parentheses. Bounded context-free languages are therefore special instances of the broader class of bounded semi-linear languages: languages of the form $L = \varphi(B)$ with $B$ semi-linear but not necessarily stratified (for example $\{a^n b^n c^n \mid n \geq 0\}$ is bounded semi-linear yet not context-free). D'Alessandro and Intrigila (Theoret. Comput. Sci. 562 and 572, 2015) settled the CE Problem affirmatively for the sparse case: every bounded context-free language is commutatively equivalent to a regular language, effectively constructible from a grammar. In contrast, the CE Problem remains open for context-free languages of exponential growth.

The Kleene closure (star) $L^*$ — the monoid of all concatenations of words of $L$ — is the sole rational operation that does not preserve boundedness: for instance the bounded (finite) set $\{ab, ba\}$ has a closure of exponential growth. Thus, even starting inside the well-understood bounded world, taking closures produces naturally occurring context-free languages of exponential growth (the closure of a context-free language is context-free), and it is nontrivial to ask which of them are commutatively regular. This is the setting of the source paper (Carpi and D'Alessandro, Theoret. Comput. Sci. 852, 2021), whose main result, Theorem 1, states: if $L$ is a bounded semi-linear language such that, in a semi-linear representation of its exponent-vector set, every generator word $\varphi(b_{ij})$ (the Ginsburg image of a base or period vector) contains at least two distinct letters (a condition shown there to be representation-independent, and equivalent to the existence of $\rho < 1$ with $|z|_a < \rho |z|$ for every $z \in L$ and every letter $a$ , where $|z|_a$ counts the occurrences of $a$ in $z$ ), and if moreover $L$ is a code, then there exists a regular code $L'$ commutatively equivalent to $L$ , so that $L^*$ is commutatively equivalent to the regular language $(L')^*$ ; the proof combines an argument from equations of words that separates the components of the semi-linear decomposition (and relies on the code hypothesis) with a decomposition of semi-linear sets into disjoint parallelepipeds. Proposition 5 of the same paper shows, without the code hypothesis (letter condition retained), that $L$ itself is commutatively equivalent to the union of a finite set and a regular code — but such a union need not be a code, so this gives no information about the closure $L^*$ . The paper's concluding remarks state that a natural continuation is to extend Theorem 1 by dropping the combinatorial restriction on the words of the language, or by relaxing the property of being a code; their final paragraph adds that the study of the conditions guaranteeing that a monoid generated by a bounded semi-linear language is commutatively regular appears as a natural issue.

Problem Statement

Let $A$ be a finite alphabet and let $L \subseteq A^*$ be a bounded semi-linear language, i.e. $L = \varphi(B) \subseteq u_1^* \cdots u_k^*$ for some words $u_1, \dots, u_k$ , the Ginsburg map $\varphi(\ell_1, \dots, \ell_k) = u_1^{\ell_1} \cdots u_k^{\ell_k}$ , and a semi-linear set $B$ of exponent vectors; $L$ need not be context-free, since the Ginsburg–Spanier theorem identifies the bounded context-free languages with the subclass whose representing semi-linear sets can be taken stratified. Determine for which such $L$ the Kleene closure $L^*$ — the monoid of all finite concatenations of words of $L$ — is commutatively regular. Specifically, Theorem 1 of Carpi–D'Alessandro (2021) proves this under two hypotheses — $L$ is a uniquely decipherable code, and every generator word $\varphi(b_{ij})$ (Ginsburg image of a base or period vector of a semi-linear representation of $L$ ) contains at least two distinct letters — the paper's concluding remarks (Section 5) ask for its extension by dropping the combinatorial restriction on the words of the language or by relaxing the property of being a code, and their final paragraph states that the study of the conditions guaranteeing that a monoid generated by a bounded semi-linear language is commutatively regular appears as a natural issue. The question has three nested parts, all open: (a) if $L$ is a bounded semi-linear code but the two-distinct-letters condition on generator words is dropped, is $L^*$ still commutatively equivalent to a regular language? (b) if the two-distinct-letters condition holds but $L$ is not assumed to be a code, is $L^*$ commutatively equivalent to a regular language? (c) in full generality — the unconditional form of the issue posed at the end of Section 5 — is $L^*$ commutatively equivalent to a regular language for every bounded semi-linear language $L$ ? An affirmative answer must supply, for each effectively presented $L$ (by a semi-linear representation of $B$ , or by a context-free grammar in the bounded context-free subcase), an effectively constructible regular language $R$ together with a bijection $L^* \to R$ preserving commutative equivalence classes of words; a negative answer must exhibit an explicit bounded semi-linear language $L$ together with a proof that no regular language is commutatively equivalent to $L^*$ . Since (c) is the unconditional form and (a) and (b) are strictly weaker sub-cases of it, it suffices to settle (c): an affirmative answer to (c) settles all three parts at once, whereas a counterexample to (c) leaves (a) and (b) open, as such a counterexample need not satisfy the code hypothesis or the two-distinct-letters condition.

References

Arturo Carpi, Flavio D'Alessandro, "On bounded linear codes and the commutative equivalence", Theoretical Computer Science 852 (2021) 185–196. DOI: 10.1016/j.tcs.2020.11.031, https://doi.org/10.1016/j.tcs.2020.11.031 (source paper)
Arturo Carpi, Flavio D'Alessandro, "On the Commutative Equivalence of Algebraic Formal Series and Languages", International Journal of Foundations of Computer Science 32(4) (2021) 341–367. DOI: 10.1142/S0129054121500192, https://doi.org/10.1142/S0129054121500192
F. D'Alessandro, B. Intrigila, "On the commutative equivalence of bounded context-free and regular languages: The code case", Theoretical Computer Science 562 (2015) 304–319. DOI: 10.1016/j.tcs.2014.10.005, https://doi.org/10.1016/j.tcs.2014.10.005
F. D'Alessandro, B. Intrigila, "On the commutative equivalence of semi-linear sets of N^k", Theoretical Computer Science 562 (2015) 476–495. DOI: 10.1016/j.tcs.2014.10.030, https://doi.org/10.1016/j.tcs.2014.10.030
F. D'Alessandro, B. Intrigila, "On the commutative equivalence of bounded context-free and regular languages: The semi-linear case", Theoretical Computer Science 572 (2015) 1–24. DOI: 10.1016/j.tcs.2015.01.008, https://doi.org/10.1016/j.tcs.2015.01.008
Arturo Carpi, Flavio D'Alessandro, Oscar H. Ibarra, Ian McQuillan, "Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity", Theoretical Computer Science 862 (2021) 97–118. DOI: 10.1016/j.tcs.2020.10.006, https://doi.org/10.1016/j.tcs.2020.10.006
Andrea Benso, Arturo Carpi, Flavio D'Alessandro, "On the Commutative Equivalence of Algebraic Structures and Related Problems", Journal of Automata, Languages and Combinatorics 30(1–3) (2025) 27–48. DOI: 10.25596/jalc-2025-027, https://doi.org/10.25596/jalc-2025-027