# A formal grammar for P?

Let $P$ be the class of formal languages that have polynomial-time decider, i.e. for each $L\in P$ there exists a Turing-machine $T$ such that for each $w\in L$ machine $T$ decides if $w\in L$ in polynomial time wrt the length of $w$.

Is it possible to define a grammar (in any "reasonable" sense) that could be used to define exactly the languages in $P$?

• Not sure about a grammar, but we know that P is equivalent to languages expressible using first order logic + a fixed point operator and ordering. – Suresh Venkat May 20 '11 at 14:10
• – Tsuyoshi Ito May 20 '11 at 15:09
• A related question asks about programming languages that implement P: cstheory.stackexchange.com/questions/5120/… Some of those answer might be relevant – Artem Kaznatcheev May 21 '11 at 1:50
• "Is it possible to define a grammar (in any "reasonable" sense) that could be used to define exactly the languages in ?" I think you are using "grammar" not in their standard meaning in the literature. I think the question is not clear, I can't see what would constitute an answer to your question. If you want something like primitive recursive functions that would capture $P$ then the answer is yes. Replace the recursion with bounded recursion on notation and it will capture exactly function in $P$. – Kaveh May 21 '11 at 6:01
• Each language is defined by its own grammar. You seem to be asking for a meta-grammar that defines the grammars of the languages in P, if I understand correctly. – Antonio Valerio Miceli-Barone May 23 '11 at 12:42