D-finiteness conjecture for shuffle closures of regular languages
D-finiteness conjecture for shuffle closures of regular languages
Let be a regular language, and let its shuffle closure be the union of all finite shuffles of :
If is the ordinary generating function of this language, then the shuffle-closure conjecture. 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.