2
$\begingroup$

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$?

Improve this question
$\endgroup$
6
  • 7
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat May 20 '11 at 14:10
  • 2
    $\begingroup$ Check cstheory.stackexchange.com/questions/12/…, cstheory.stackexchange.com/questions/869/…, and cstheory.stackexchange.com/questions/1897/…. $\endgroup$ – Tsuyoshi Ito May 20 '11 at 15:09
  • 2
    $\begingroup$ A related question asks about programming languages that implement P: cstheory.stackexchange.com/questions/5120/… Some of those answer might be relevant $\endgroup$ – Artem Kaznatcheev♦ May 21 '11 at 1:50
  • 4
    $\begingroup$ "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$. $\endgroup$ – Kaveh May 21 '11 at 6:01
  • $\begingroup$ 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. $\endgroup$ – Antonio Valerio Miceli-Barone May 23 '11 at 12:42
2
$\begingroup$

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.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1196

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – user3355 May 23 '11 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy