Abstract:

This paper studies the set $\mathcal{L}_p(\Sigma)$ of prefix-free languages over some alphabet $\Sigma$. It is proved that Levi's lemma holds for such languages, and also that the theory of the algebra $\mathcal{L}_p(\Sigma)$ with concatenation is undecidable. It is established that the algebra $\mathcal{L}_p(\Sigma)$ without the empty language is elementarily equivalent to the algebra of all words over an infinite alphabet.