## Any result or conjecture of computaional complexity of formal languange with rational generating function?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

2
As far as I can tell, a formal language with rational generating function can be arbitrarily hard to recognize. Consider the language with one word of each length $n$ such that each new word describes $n$ more digits of Chaitin's constant... – Qiaochu Yuan Sep 17 at 16:37
@Qiaochu,is the language recursively enumerable?Or is the language a C.E set? – XL Sep 17 at 18:01
en.wikipedia.org/wiki/Chaitin%27s_constant – Benjamin Steinberg Sep 18 at 13:04

## 1 Answer

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}.$$

Added to address the OP's comment below

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.

-

@Benjamin,Yes,usually,when we talk about formal language,we assume,that the language is at least a c.e.set.Yes,we can talk about language that is not c.e.set,which is in the area of computability or unsolvability .Anyway,you have made some clarification,thank a lot.And Qiaochu's construction is really a c.e.set – XL Sep 18 at 14:40
Let me add an edit to address this. – Benjamin Steinberg Sep 18 at 15:15
It seems that languages with such rational generating function go through all classes of all computational complexity – XL Sep 18 at 16:31
Yes, that would seem to be the case since one has sequences with arbitrary complexity in computing their prefixes I believe. – Benjamin Steinberg Sep 18 at 17:02
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9196914434432983, "perplexity_flag": "middle"}