[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

*SORRY*

To my complete dismay, I really misread something. The complexity stuff 
from section 3 I quoted was for "non-fixed" k. Which is in total 
accordance with what is written in paragraph 2. For unary k it is in NP, 
for non-unary in NE. And indeed there is this proof for LR(k) testing is 
in P. *OOPS* again... Seeing it in this light, all this stuff really 
makes much sense to me. Just to check, this means SLK does table 
generation in polynomial time in most cases, but not all, like for the 
grammar given there. Is this correct now?

As the proof is far beyond of what I can understand in less than a day I 
am afraid, can you tell me if it is constructive, i.e. if you can use it 
to actually generate the parse table with it?

By the way, Sarah, are you the auhor of the docs at 
http://home.earthlink.net/~parsersinc/ ?

Thanks again :)

Oliver

Oliver Zeigermann wrote:

> sarah2geller wrote:
> 
>>Clearly, if SLK could solve an NP-complete problem in polynomial 
>>time, that would constitute a proof that P=NP. But the conjecture 
>>given is that P!=NP, so it seems that you misread something.
> 
> 
> Not quite sure, let's do it step by step, quoting from the beginning of 
> http://home.earthlink.net/~parsersinc/doc/conjecture.html:
> 
> 
>>The complexity of testing context-free grammars for the SLL(k) property 
>>was first investigated by Hunt, Szymanski, and Ullman (1975). They 
>>showed that the problem is solvable in polynomial time if the value of k is fixed ahead of time.
>>That is, if k is not a parameter of the problem, then SLL(k) recognition
>>is in P, the class of problems solvable in polynomial time.
> 
> 
> Which from my understanding is clearly false as this article *at most* 
> proves it is in NP as the lower bound estimation was for 
> "non-deterministic" time. This is because for a "non-deterministic" TM 
> it is polynomial time, thus the lower bound is clearly in *NP*, not *P*. 
> Do you agree? Maybe I am missing something, can you see what this might be?
> 
> Thanks in advance and cheers :)
> 
> Oliver
> 
> 
> 
>  
> 
> Yahoo! Groups Links
> 
> To visit your group on the web, go to:
>  http://groups.yahoo.com/group/antlr-interest/
> 
> To unsubscribe from this group, send an email to:
>  antlr-interest-unsubscribe at yahoogroups.com
> 
> Your use of Yahoo! Groups is subject to:
>  http://docs.yahoo.com/info/terms/ 
> 
> 
> 




 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:
 http://docs.yahoo.com/info/terms/