<p>According to the Internet, <a href="http://ieeexplore.ieee.org/xpl/abstractMetrics.jsp?tp=&amp;arnumber=5597971&amp;url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5597971" rel="nofollow">there's a way to get an L-system's rules by it's string</a>, unfortunately I can't read it because it's behind a paywall.</p>

<p><strong>Question:</strong> If that paper is right, is it possible to make an algorithm, based on L-systems, to recursively reduce let's say a blob of 64MB of zeros and ones down to:</p>

<ul>
<li>A <strong><em>"small"</em> starting axiom</strong>.</li>
<li>A <strong>set of variables/constants/you-name-it</strong>.</li>
<li>A <strong>set of rules</strong>.</li>
<li>The <strong>number n of iterations</strong> required.</li>
</ul>

<p><strong>/Question End</strong></p>

<p>Compression is all about entropy and something in my guts says this isn't possible, I'd like someone with more experience to confirm it.</p>

CC BY-SA 3.0
2013-09-12T12:39:17.297Z
Isn't this essentially how Lempel-Ziv-etc works?
Jeffε
CC BY-SA 3.0
2013-09-12T15:03:46.467Z
@JɛﬀE Isn't LZ- just one pass?
toqueteos
CC BY-SA 3.0
2013-09-13T04:23:31.263Z
_all_ grammars can double as [compression algorithms](http://en.wikipedia.org/wiki/Grammar-based_code). & $K(x)$ from kolmogorov complexity is the ultimate grammar compression.
vzn
<ds.algorithms><computability>
Is it possible a recursive compression algorithm based on L-systems or a variant?
toqueteos
# Is it possible a recursive compression algorithm based on L-systems or a variant?

(Asked by: username_0 on 2013-09-12)

According to the Internet, [there's a way to get an L-system's rules by it's string](http://ieeexplore.ieee.org/xpl/abstractMetrics.jsp?tp=&arnumber=5597971&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5597971), unfortunately I can't read it because it's behind a paywall.

**Question:** If that paper is right, is it possible to make an algorithm, based on L-systems, to recursively reduce let's say a blob of 64MB of zeros and ones down to:

* A ***"small"* starting axiom**.
* A **set of variables/constants/you-name-it**.
* A **set of rules**.
* The **number n of iterations** required.

**/Question End**

Compression is all about entropy and something in my guts says this isn't possible, I'd like someone with more experience to confirm it.

**Tags:** ds.algorithms, computability

> **Comments:**
> **username_1**: Isn't this essentially how Lempel-Ziv-etc works?  
> **username_0**: @JɛﬀE Isn't LZ- just one pass?  
> **username_2**: _all_ grammars can double as [compression algorithms](http://en.wikipedia.org/wiki/Grammar-based_code). & $K(x)$ from kolmogorov complexity is the ultimate grammar compression.  

---

## 0 answers

