# 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

## 2 Answers

If you have notions of linear logic, you might want to have a look at the article Soft Linear Logic and Polynomial Time [1] that describes a variant of linear logic (some of the deduction rules have been modified) whose formulas are only provable by proof that are polynomial-time algorithm.

Abstract: We present a subsystem of second order Linear Logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice-versa.

If you are not talking about "a grammar", but rather a grammar formalism, or class of grammars, then this might be useful: the class of languages generated by Range Concatenation Grammars (RCG) is exactly PTIME (for a proof, see Bertsch and Nederhof; for an introduction to RCG, see various papers by Boullier or the Wikipedia article).

• This looks very interesting. It seems to me that this construction somewhat blurs the difference between a syntactic method to define a language and a computational model (algorithm) to decide a language. – user3355 May 23 '11 at 9:59