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! :)
If $P$ and $Q$ are languages closed under prefix, then $P\cup Q$, $P\cap Q$, $P \cdot Q$, $P/Q$ are also closed under prefix. Also you can think of such a language $L$ as a directed tree. Define the graph/tree $G = (V,E)$ where $V = L$ and $$E = \{(\mathit{prefix}(w),w) \mid w\in L \}$$ (the words are the nodes and the parent of every word is its prefix). Note that I assume that $\mathit{prefix}(x) = \varepsilon$ for all $x\in\Sigma$, meaning that the prefix of a single symbol is the empty word. Thus the root of the tree constructed above is the empty word. The constructed tree can be easily transformed to a DFA recognizing the language (I think you can see how).
Let $L$ be an arbitrary language. Since the set of all words is countable, we can think of $L$ as a subset of $\mathbb{N}$. Let $\ell_i = 1$ if $i \in L$, and $\ell_i = 0$ if $i \notin L$. Define the language $L'$ of all words of the form $\ell_1 \ldots \ell_n$. The language $L'$ inherits many properties of $L$, and is prefix-closed.
