Timeline for Generating a set of minimal-length strings that, together, invoke every production of a context free language
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Dec 6, 2015 at 2:53 | vote | accept | Patrick Collins | ||
| Jul 18, 2014 at 22:25 | comment | added | babou | @vzn The minimality requested is on the size of each string with respect to the rule it is supposed to invoke. The answer I give is minimal in that sense. You cannot use a string minimal for one rule as the minimal string for any rule it invokes, as it may not be minimal for these other rules. In particular, two rules can share the same string only if their minimal derivations have the same length. Anyway, minimality on the number of strings is not in the OP's question. I do not believe there is enough original material for a paper. It is too complex for pseudo-code that cannot be tested. | |
| Jul 18, 2014 at 16:24 | comment | added | vzn | already +1 for the effort. the idea of finding size-minimal terminal strings for each terminal is a nice approach but also presumably wont lead to totally minimal sets, ie is a heuristic that will finish with local minima for some cases. as cited above, think a good writeup needs pseudocode at least. maybe a paper? :) | |
| Jul 18, 2014 at 0:07 | comment | added | babou | @vzn Here is, I hope, my last instalment. Hopefully, even if you do not trust me, you will trust Don Knuth. As I expected, it is a matter of and-or graph extension of Dijkstra's algorithm (which is also what I did). But Knuth's paper is really nice. It is all summarized at the beginning of my answer. | |
| Jul 18, 2014 at 0:00 | history | edited | babou | CC BY-SA 3.0 |
added short presentation
|
| Jul 16, 2014 at 23:12 | comment | added | babou | @vzn I doubt Greibach or Chomsky normal form will bring any light. This is grammar dependent more than language dependent. Changing the grammar changes the problem. Actually, I first thought it was a homework dump. The minimality requirement does give it some interest, as finding a good algorithm was less obvious, especially my last version. I wrote the proof because I could not convinced myself any other way that it actually works. It is somehow less intuitive that the straight Dijkstra's algorithm from which I derived it. | |
| Jul 16, 2014 at 22:37 | comment | added | vzn | minimization & "coverings" are common considerations in the theoretical literature. further thought, maybe a normal form either Greibach or Chomsky could be key to understanding it better (there is some connection there also with removing unproductive terminals/nonreachable symbols). think this is worthwhile question for tcs.se, may ask it at some pt there & cite this one (afaik migrations tend to lose comments.) | |
| Jul 16, 2014 at 21:58 | comment | added | babou | @vzn What could be in the literature is the extension of Dijkstra's shortest path algorithm to and-or graphs. Unfortunately, I do not have access to resources for finding out. I could write it up in a simplified form, without the CF grammar stuff. But then, I do not think it is a big deal. But it does gives the right hints to implement with low complexity. | |
| Jul 16, 2014 at 21:47 | comment | added | babou | @vzn I doubt this problem has been published, because I do not see an application that does require this minimality. The useless symbols elimination algorithm is a classical technique, found probably in all textbooks on CF languages. And, as I said, it has some applications in general CF parsing. I never heard of pushing it further for producing test sentences. I chose to try explain its derivation, rather than give pseudo code. As it is the answer is already very long. Maybe in a second answer, if that is acceptable on the site ... as the text is becoming too long to handle. | |
| Jul 16, 2014 at 21:25 | history | edited | babou | CC BY-SA 3.0 |
added 6495 characters in body
|
| Jul 16, 2014 at 2:19 | comment | added | vzn | looks plausible but suggest it needs to be converted at least to pseudocode. also it seems plausible the problem or near variants has been studied in the literature somewhere... | |
| Jul 16, 2014 at 1:20 | history | edited | babou | CC BY-SA 3.0 |
improved presentation and removed typos.
|
| Jul 12, 2014 at 1:13 | history | answered | babou | CC BY-SA 3.0 |