complexity theory – Can you say anything interesting about a language knowing only that it is prefix-closed?


Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w in L$, and $u$ is any prefix of $w$, then $u in L$).

Knowing only this, can you give any positive or negative decidability or complexity results about $L$?

Thanks! 🙂