D-finiteness conjecture for shuffle closures of regular languages

Let L\mathcal{L} be a regular language, and let its shuffle closure be the union of all finite shuffles of L\mathcal{L}:

L ⁣=nL ⁣n.\mathcal{L}^{\sqcup\!\sqcup}=\bigcup_n \mathcal{L}^{\sqcup\!\sqcup n}.

If L(z)L(z) is the ordinary generating function of this language, then the shuffle-closure conjecture. L(z)L(z) is D-finite.

Shuffle closure does not preserve regularity, and adjoining shuffle closure and the shuffle product to regular languages can generate all recursively enumerable languages. The conjecture asserts that the generating function nevertheless remains D-finite for the shuffle closure of a regular language; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Marni Mishna and Mike Zabrocki, “Analytic aspects of the shuffle product”, arXiv:0802.2844 (2008).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.