Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Yeah, I'll take that. –  Big Endian Mar 29 '13 at 3:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.