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.
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.
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.
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 http://www.mat.univie.ac.at/~slc/wpapers/s61Alablam.html.
No comments:
Post a Comment