Timeline for Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2015 at 15:01 | comment | added | Danny | Of course this topic normally deals with arbitrary strings about larger alphabets, too. | |
| Jul 26, 2015 at 15:00 | comment | added | babou | Well. I am asking because I have improved my result, but it is signficant work to write down, and I was wondering whether you are interested. Of course, asymptotics is the same, but absolute size may be reduced signiicantly | |
| Jul 26, 2015 at 14:57 | comment | added | Danny | My interests are mostly about asymptotics, but you are right, the exact size is also very interesting, so thanks again for your answer. The original purpose of SLPs is about compressing a single word. But there is related work in the recent literature about compressing finite languages, too. | |
| Jul 26, 2015 at 14:13 | comment | added | babou | Thanks. So given your application, I guess absolute optimality is as important as asymptotic growth optimality? Or is it? This might just be an example for complexity assessment? Your title says "minimal size", not "minimal asymptotic size growth" --- But is your existing application for single word languages, or is it also for languages like $L_n$ ? --- And I suppose you use strings that are more structured than $a^k$. | |
| Jul 26, 2015 at 13:53 | comment | added | Danny | @babou The empty rule hase size 0 in this definiton. Yes there is an application. There are so called straight line programs (SLPs) to compress words with context free grammars. The the size of a grammar as defined in my question is the usual way in various papers to define the grammar size in this context. If we consider some kind of normal form like CNF it is also possible to count the rules since it is nearly the same. My question comes from this context, because in my opinion it is senseful to think about grammars as a compressor for languages instead of single words, too. | |
| Jul 26, 2015 at 13:27 | comment | added | babou | Do you consider the empty rule $U\to\lambda$ as having size $0$ or size $1$. --- Is there a specific reason for this choice of grammar size definition, or was it just arbitrary? You could have considered also a cost of 1 for each rule. --- Besides, I am curious as to the applications or context for this problem. Do you have any? | |
| Jul 24, 2015 at 20:22 | history | tweeted | twitter.com/#!/StackCompSci/status/624676013918814208 | ||
| Jul 24, 2015 at 17:34 | answer | added | babou | timeline score: 3 | |
| Jul 24, 2015 at 16:44 | vote | accept | Danny | ||
| Jul 24, 2015 at 12:22 | answer | added | Yuval Filmus | timeline score: 6 | |
| Jul 24, 2015 at 11:39 | answer | added | Raphael | timeline score: 0 | |
| Jul 24, 2015 at 11:37 | answer | added | WhatsUp | timeline score: 0 | |
| Jul 24, 2015 at 11:36 | comment | added | Hendrik Jan | Adding $A_4\to a$ and $A_4\to \lambda$ would help a lot in your case, and seems to be applicable in general. | |
| Jul 24, 2015 at 11:33 | history | edited | Raphael |
edited tags
|
|
| Jul 24, 2015 at 11:04 | history | asked | Danny | CC BY-SA 3.0 |