# $\mathsf{P}$ is the closure of [finite set] under [operation between languages]

I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\Sigma^*) \to \mathcal{P}(\Sigma^*)$ such that $\mathsf{P}$ is the smallest class containing $F$ and closed under $\otimes$.

Ideally, the operations should be computable and natural in some intuitive sense, and the languages in $F$ quite simple. I'd like to avoid, say, that a language of $F$ encodes all polytime machines, or that one operation "runs" a Turing machine.

• The descriptive complexity characterization of $\mathsf{P}$ as $(\mathsf{FO} + \mathsf{LFP})$, while not formally what you're asking for, has a similar flavor. – Andrew Morgan Jul 7 '16 at 12:45
• @AndrewMorgan: Thanks! I do know this characterization, and other similar ones, but indeed, my statement is quite restrictive—and on purpose so! While working on language-theoretical frameworks expressing descriptive complexity classes, I ended up with a statement of the question's form, hence I'm wondering if there are others to compare it to. Cheers! – Michaël Cadilhac Jul 7 '16 at 13:48
• You probably are aware of the characterizations of the function class $\mathsf{FP}$ of this form, are you? – Jan Johannsen Jul 7 '16 at 14:54
• Bellantoni and Cook, a new recursion-theoretic characterization of the polytime functions, 1992. – Kaveh Jul 8 '16 at 0:37
• – Kaveh Jul 8 '16 at 0:39