Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:09:04Z http://mathoverflow.net/feeds/question/8262 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? Qiaochu Yuan 2009-12-08T22:26:27Z 2010-02-24T23:43:43Z <p>Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:</p> <ul> <li>If $L$ is regular, then $f_L$ is rational. </li> <li>If $L$ is unambiguous and context-free, then $f_L$ is algebraic.</li> </ul> <p>Does there exist a natural family of languages $\mathcal{L}$ containing the context-free languages such that if $L \in \mathcal{L}$, then $f_L$ is <a href="http://en.wikipedia.org/wiki/Holonomic#Holonomic_function" rel="nofollow">holonomic</a>? Is that class of languages also associated to a natural class of automata? </p> <p>This question is prompted by a remark in Flajolet and Sedgewick where they assert that there is no meaningful generating function formalism associated to context-sensitive languages because of the significant undecidability issues. However, holonomic functions have proven a robust and incredibly useful framework in combinatorics, so I think this is a natural question to ask.</p> http://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic/8288#8288 Answer by Greg Kuperberg for Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? Greg Kuperberg 2009-12-09T01:44:13Z 2009-12-09T01:44:13Z <p>I don't know the topic well enough to give you a complete answer, but two things. First, Chomsky and Schutzenberger proved that <em>unambiguous</em> context-free languages have an algebraic generating function. These are languages for which there is a context-free grammar that accepts each word in only one way. Or more generally and more weakly, they showed that the number of acceptances, as distinct from the number of words, has an algebraic generating function. <a href="http://dx.doi.org/10.1016/0304-3975%2887%2990011-9" rel="nofollow">There is a paper by Philippe Flajolet</a> in which he proves that certain CFLs have no unambiguous grammar exactly by showing that the generating function is transcendental. Flajolet is also interested in holonomic generating functions, but I did not see any clear statement as to whether the g.f. of an ambiguous CFL can be non-holonomic. Flajolet is surely a good person to ask about the entire question.</p> <p>Second, I can't resist mentioning an unfinished project from a while ago that might help you as a survey. <a href="http://www.math.ucdavis.edu/~greg/zoology/" rel="nofollow">Complexity Zoology</a> is a computer-assisted compilation of inclusions and separations of language classes, to go with the much better known <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo" rel="nofollow">Complexity Zoo</a> living survey started by Scott Aaronson. The Complexity Zoo moved to Stanford, so for now all of my links are broken, but Zoology knows things that would be difficult to add to the Zoo without its help. You can learn pretty quickly that there are not very many language classes between CFL and things that are clearly #P-hard to count, or harder. One candidate is GCSL, which means CSL with the restriction that all replacement rules make the words grow. Although in light of the first comment, looking at the next things after CFL is a little off the mark; DCFL or deterministic CFL is fairly standard and is contained in unambiguous CFL.</p> <p>My guess is that holonomic sequences are an enumerative intermediate that doesn't show up easily in complexity theory.</p> http://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic/15288#15288 Answer by Jacques Carette for Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? Jacques Carette 2010-02-14T21:52:21Z 2010-02-14T21:52:21Z <p>I think it depends on your notion of natural''. I would expect that if you allow grammar definitions to use the $\Theta$ operator (as well as the usual sums and products of CFGs), then you should get 'exactly' the holonomic class. The $\Theta$ operator is essentially the derivative (that is what it does on GFs).</p> <p>There might be a more intrinsic classification in terms of Species.</p> http://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic/15481#15481 Answer by Martin Rubey for Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? Martin Rubey 2010-02-16T19:00:09Z 2010-02-16T19:00:09Z <p>I vaguely remember that the paper by Marni Mishna and Mike Zabrocki <a href="http://arxiv.org/abs/0802.2844" rel="nofollow">Analytic aspects of the shuffle product</a> sheds some light on the subject.</p> http://mathoverflow.net/questions/8262/is-there-a-natural-family-of-languages-whose-generating-functions-are-holonomic/16326#16326 Answer by Marni Mishna for Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)? Marni Mishna 2010-02-24T23:43:43Z 2010-02-24T23:43:43Z <p>I have considered this problem for a while now. I agree with Greg that the parallels with complexity theory seem to end at unambiguous context free. The quality that makes a word difficult to recognize diverges from what makes a language difficult to enumerate: e.g. { a^n b^n c^n: n a posint} is easy to count. On the other hand, D-finite sequences are unable to handle a certain notion sparseness, (i.e. {a^(2^n): n a posint}) because they tend to give rise to natural boundaries in the generating functions. </p> <p>As for Jacques' comment, it is true that there is a differential operator in species, but that does not mean that you can model solutions to differential equations easily. If you take an iterative approach a la Chomsky Schützenberger to generate the combinatorial objects, you need to ensure convergence of your language. (the paper cited above by Martin actually needs a partial retraction on this point) It is easy to show convergence if you can use Theta, which is actually x d/dx, but you cannot use theta to build all linear ODEs with polynomial coefficients. </p> <p>Along this line, if you restrict yourself to solutions of smaller families of differential equations, there are several combinatorial interpretations, often in terms of rooted trees. </p> <p>Or, maybe a completely different approach is warranted, for example the notion of level of Géraud Sénizergues or the recent work of Labelle and Lamathe <a href="http://www.mat.univie.ac.at/~slc/wpapers/s61Alablam.html" rel="nofollow">http://www.mat.univie.ac.at/~slc/wpapers/s61Alablam.html</a>.</p>