most recent 30 from http://mathoverflow.net 2013-05-25T00:17:20Z http://mathoverflow.net/feeds/question/107383 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107383/any-result-or-conjecture-of-computaional-complexity-of-formal-languange-with-rati XL 2012-09-17T14:18:02Z 2012-09-18T15:25:12Z

<p>As we know that context-free language is in P,any result or conjecture of computaional complexity of formal languange with rational generating function?And more,any result or conjecture of computaional complexity of formal languange with algebraic generating function?</p>

http://mathoverflow.net/questions/107383/any-result-or-conjecture-of-computaional-complexity-of-formal-languange-with-rati/107464#107464 Benjamin Steinberg 2012-09-18T13:11:50Z 2012-09-18T15:25:12Z

<p>To clarify Qiaochu's comment and make it explicit, I claim there are uncountably many languages with a rational generating function (namely, $\dfrac{1}{1-x}$). Only countably many of these can even be recursively enumerable. Namely, let $w\in \lbrace 0,1\rbrace^{\omega}$ be a right infinite word. Let $L(w)$ be the language of prefixes of $w$. Then $L(w)$ has a unique element of length $n$ for each $n$ and one can recover $w$ from $L(w)$. Thus there are uncountable many languages of the form $L(w)$. Since it has one word of each length, its generating function is $$1+x+x^2+\cdots = \dfrac{1}{1-x}.$$</p> <p><strong>Added to address the OP's comment below</strong> </p> <p>There are trivially sequences $w\in \lbrace 0,1\rbrace^{\omega}$ whose language $L(w)$ is r.e. but not recursive. Namely, we can view $w$ as the characteristic function of a set $A$ of natural numbers. Clearly membership in $L(w)$ is the same as determining membership in $A$ as far as decidability goes, although there is perhaps some complexity blowup since to check if a string of length $n$ belongs to $L(w)$ we must check which of the first $n$ natural numbers belong to $A$ and conversely to check if an integer $n$ is in $A$, we have to look potentially at all bit strings of length $n. So this seems like a PSPACE blowup.</p>