Timeline for Permutation phrases with LR parsing
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27, 2017 at 22:33 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 28, 2017 at 22:18 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 28, 2017 at 21:44 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 29, 2017 at 21:25 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 29, 2017 at 21:15 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 30, 2017 at 20:36 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 28, 2017 at 20:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 29, 2017 at 19:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 30, 2016 at 18:58 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 30, 2016 at 18:10 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 31, 2016 at 18:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 1, 2016 at 18:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 1, 2016 at 17:29 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 2, 2016 at 16:54 | answer | added | PMar | timeline score: 1 | |
| Aug 1, 2016 at 8:19 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 2, 2016 at 7:42 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 2, 2016 at 7:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 14, 2014 at 15:34 | comment | added | Jurgen Vinju | I am wondering what happens to the size of the tables if we would generate the permutations in Chomsky normal form. Would that not shrink the problem back to something manageable, i.e. polynomial? Especially with parsing algorithms that do this normalization implicitly (BRNGLR and GLL), this seems a relevant question. | |
| Sep 5, 2013 at 0:48 | comment | added | Sylvain | @D.W. In the original question, the permutations allowed by a grammar with permutation phrases are not fixed in advance. The same holds of the permutation languages of Yuval Filmus in the linked paper: all the permutations of a fixed length are allowed. | |
| Sep 21, 2012 at 0:30 | comment | added | Tsuyoshi Ito | @Sylvain: Now I see (after eight months). Thanks for the explanation! | |
| Mar 23, 2012 at 7:51 | answer | added | Uiy | timeline score: 0 | |
| Jan 27, 2012 at 20:25 | history | tweeted | twitter.com/#!/StackCSTheory/status/162994783143477249 | ||
| Jan 27, 2012 at 20:13 | comment | added | Sylvain | @Tsuyoshito Ito: In LR(1) parsing a DPDA equivalent to the input grammar is first constructed and then run against the string to recognize. As there exists a linear-sized CFG with permutation phrases for every permutation language, Yuval Filmus' paper (which is more comprehensive than his answer on cstheory: see cs.toronto.edu/~yuvalf/CFG-LB.pdf) shows that no such DPDA can be of polynomial size in the size of the input grammar. | |
| Jan 27, 2012 at 19:35 | comment | added | Tsuyoshi Ito | @Sylvain: Can you elaborate on how question 4962 relates to this one? In question 4962, permutation is fixed for each input length, and the strings to be permuted changes. In the current question, we do not fix the permutation. So I fail to see any real connection between them. | |
| Jan 27, 2012 at 17:07 | comment | added | Sylvain | I hadn't looked at the paper on LL(1). Indeed, the implemented parser is no longer a PDA. I still do not believe in the existence of a "reasonably-sized table", since membership for commutative context-free grammars is NP-complete (see e.g. dx.doi.org/10.3233/FI-1997-3112), but it's true that the hard instances might not be LR(1). | |
| Jan 27, 2012 at 16:28 | comment | added | Alex ten Brink | @Sylvain: I didn't know about the exponential worst case of LR(1) parsers - it's nearly always skimmed over in analyses. Luckily, the worst case seems to be quite rare, contrary to my method that always gives the full size blowup. About that other question: I saw it before, and it does indeed mean that modifying just the grammar or automaton won't be enough. I was however hoping that one could store extra information on the LR-stack, just like the LL method in the paper I linked, so the normal LR(1) table sizes are maintained. | |
| Jan 27, 2012 at 16:23 | history | edited | Alex ten Brink | CC BY-SA 3.0 |
added 75 characters in body
|
| Jan 27, 2012 at 16:16 | comment | added | Sylvain | About the rest of your question: cstheory.stackexchange.com/questions/4962/… shows an exponential lower bound on the size of a CFG for permutations, and by the usual polynomial construction of CFGs from PDAs, this entails an exponential lower bound on the size of the PDA as well. | |
| Jan 27, 2012 at 16:09 | comment | added | Sylvain | The complexity of LR(1) parsing is already exponential in the size of the grammar without permutation phrases---except if you implement an "on the fly" computation of the parser, but then it feels more like an Earley parser than like a genuine LR(1) one. | |
| Jan 27, 2012 at 14:17 | history | asked | Alex ten Brink | CC BY-SA 3.0 |