I am writing a program to work with L-systems (Lindenmayer Systems) and I need to know how much memory to allocate for the strings, but my problem is clearly a math problem, not a programming one. Here's my situation: I have an arbitrary starting condition for an L-system with arbitrary rules being iterated an arbitrary number of times. I need obtain an estimate for the length of the final string. This estimate may be too high, but under no condition may it be too low. This seems like it should be an easy problem, but once I started I found myself a little stuck. Can anybody help me?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Well, a large upper bound would be if every character in the axiom were replaced with the longest rule. This is a pretty bad estimate in general--though you might be fine with that.
Still, I feel like something better could be attained. At the very least, the growth of an L-system is nicely behaved; you might try running a few iterations, finding a generous exponential upper bounding function, and extrapolating.