Talk:L-system

Tilings

This paragraph is unclear to me:

As an L-system these tilings are called Penrose's rhombuses and Penrose's tiles. Above pictures were generated for n=6 as an L-system. If we properly superimpose Penrose tiles as an L-system we get next tiling:

It doesn't define what n is. It doesn't define what "properly superimpose as an L-system" means. It doesn't say which L-system was used to generate those images. I can't guess these from context. --LC

in the canter dust example,it contains a line of "constant" about some 60 degrees. what's that line doing there? I think it is wrong.

in the Koch snowflake example, shouldn't the plus and minus sign be part of the alphabet?

i think the penrose tiling example is a bit forced. Penrose tilings are aperiodic. So, i doubt it can be reduced to a string replacement system.

also, i'm not sure L-Sytem has a place in serious math. If it does, it is or relates to formal logic. Should there be a mention?

thanks.

Xah P0lyglut 11:18, 2004 Jan 15 (UTC)

Constants?

In Example 3, Cantor Dust, what are the constants for? (I'm not even sure if that's one, two, or three constants you're trying to list.) You never seem to use them.

Concerning the Koch curve shouldn't + and - be constants (clearly there're no productions for them). According to the definition stated, the alphabet consists of variables, hence I disagree with the poster asking that they should be included in the alphabet.

Koch curve

I would like to see one higher order iteration (n=20 ?) of the Koch curve. IMO, the result is illustrative and pretty impressive especially for people new to the subject.

Need new Penrose time images

The three images of Penrose tilings are all untagged, and they don't have authorship info (dating from before "the big conversion"). I guess when the next untagged-image jihad gets underway these images may well meet with infinite justice, so we need to start thinking about replacements for them ASAP. It's a bummer, as they're really attractive images. -- Finlay McWalter | Talk 15:17, 7 October 2005 (UTC)

These images were made by me with Winfract version 18.21, and we can tag them as public domain. I'll do that right the way. --xJaM 14:02, 21 October 2005 (UTC)

Example 1 seems strange to me

Lindenmayer's original L-system for modelling the growth of algae.

variables : A B

constants : none

start  : A

rules  : (A → AB), (B → A)

which produces:

n=0 : A → AB

n=1 : AB → ABA

n=2 : ABA → ABAAB

n=3 : ABAAB → ABAABABA

I would expect it to look like this more in keeping with how the others are shown:

n=0 : A

n=1 : AB

n=2 : ABA

n=3 : ABAAB

n=4 : ABAABABA

Am I missing something? Hogan 02:11, 29 April 2006 (UTC)

Yes, you are right - the format of Example 1 was not consistent with the format of other examples. I have fixed it. Gandalf61 08:16, 2 May 2006 (UTC)

As I had problmes to follow the intial example I would suggest this (only in the first example, to make the principle more clear):

   n=0:         A              start/axiom/initiator
               / \
   n=1:       A   B            the single A spawns into an A followed by a B
             /|    \
   n=2:     A B     A          the former A again spawns into AB, B turnes into A
           /| |     |\
   n=3:   A B A     A B        note all A's producing a copy of themself in the first place, then a B, which turns
         /| | |\    |\ \
   n=4: A B A A B   A B A      into an A one generation later, starting to spawn/repeat/recurse then

which is inspired by the (existing) external link [1] (13 MB!). Maybe an image instead of the ASCII graphic would be even more apropriate?

Also the Fibonacci example 2 refers to example 1. Then ex. 1 should have a start/axiom/initiator of B (and the above diagram extended accordingly), else the reference doesn't hold true! - Deerwood (talk) 05:02, 1 July 2008 (UTC)

Example 1 seems clearly wrong. Also, it's unclear what the terminology (A → AB), (B → A) means. Does (A → AB) mean "A gets followed by AB"? Or does it mean "A gets replaced by AB"?

If (A → AB means "A gets followed by AB" then example 1 is clearly incorrect. In that case, we would have

n=0 : A

n=1 : AAB

n=2 : AABA

n=3 : AABAAB

n=4 : AABAABA and so on. In short, you'd always get nothing but a repetition of AAB over and over again. Since that's obviously not what an L-system does, your explanation doesn't seem to have made clear what's going on.

If, on the other hand, (A → AB) means "A gets replaced by AB," then your first example is also clearly incorrect. In that case, we would get

n=0 : A

n=1 : AB

n=2 : ABA

n=3 : ABAB

n=4 : ABABA and so on. In short, a mere repetition of AB over and over again. This is also clearly not what an L-system does.

So either I'm completely missing something, or the rules you've given are being used in some way that's not at all clear from your explanation, or Example 1 is simply incorrect.

Either way, some more clarification of exactly what the symbols mean and precisely how the rules are supposed to operate would be a big help. — Preceding unsigned comment added by 140.211.8.7 (talk) 20:28, 31 October 2013 (UTC)

Another example: Heighway dragon

Another nice example is a dragon curve. It is described by the following L-system:

variables : L R

constants : + −

start  : R

rules  : (R → R+L), (L → R−L)

meaning, respectively:

L, R — step forward

plus — turn right by 90°

minus — turn left by 90°

Some initial strigns are:

n=0 : R

n=1 : R+L

n=2 : R+L+R−L

n=3 : R+L+R−L+R+L−R−L

n=4 : R+L+R−L+R+L−R−L+R+L+R−L−R+L−R−L

CiaPan 20:53, 6 October 2006 (UTC)

Merge with graftal article?

I've added graftal to the "See Also" section, but does it really need a separate article? There doesn't seem to be a whole lot of difference between L-systems and graftals. Perhaps the articles should be merged together. What do you think? -- Sakurambo 桜ん坊 13:53, 15 May 2007 (UTC)

This is a good suggestion, since, as you noted, there is not much difference. In fact, a graftal is an L-System. So I definitely support this idea. Kwvan (talk) 18:29, 12 October 2009 (UTC)

Better examples

Some of the examples given in this article are a bit rubbish. The first example provides no explanation of what is going on. What does the string "ABAABABAABAABABAABABAABAABABAABAAB" have to do with algae? If the only important information is the length of each sequence, then how does this differ from Fibonacci's modelling of rabbit populations? The second example is completely redundant — the first example also generates a Fibonacci sequence, in case you hadn't noticed, and in any case, there's a much simpler algorithm for calculating this series, so in what way is this a useful example of the capabilities of an L-system? Examples 5 and 9 are quite useless without the rules used to produce these figures. -- Sakurambo 桜ん坊 14:10, 15 May 2007 (UTC)

The Penrose tiling algorithm is given at the article of the same name, though the syntax is different. I could try translating between notations myself, but I am loathe to introduce errors. The modified Koch curve I'm not sure about, from the Koch curve page the standard curve uses

   Alphabet : F
   Constants : +, −
   Axiom : F++F++F
   Production rules:
   F → F−F++F−F 

I am guessing that the variant would alternate the production rule between F → F−F++F−F and F → F+F--F+F though this is pure speculation from the description, I have no idea how it was actually generated. As to the criticism of the first examples, algae was merely what he was historically trying to model the growth of, I don't think it is meant to represent the useful capabilities of the system, more to provide an example that correlates it with a well known algorithm. Nazlfrag (talk) 06:27, 13 June 2008 (UTC)

Explanations

I added an explanation ASCII art to the first example and hope this doesn't get deleted immediately without discussion.

Visitors/readers of an encyclopedia ain't expected to be mathematicians, programmers or specialists in any way, are they? Readers should at least be able to understand the concept/essentials ... may be, one or the other reader then gets inspired to read on, learn and understand? And, may be, contribute? - Deerwood (talk) 03:38, 3 July 2008 (UTC)

IFS

Is there a reference for the statement that "L-systems can also be used to generate self-similar fractals such as iterated function systems"? Richard Pinch (talk) 21:17, 16 July 2008 (UTC)

I removed that bit about IFSs in the intro, as I thought it was stated in a misleading way. In my understanding, IFSs and L-systems are considered two different methods both able to generate fractal objects. Oftentimes an L-system (usually with Turtle interpretation) and an IFS can generate the same object (such as the Koch curve) however in these cases we wouldn't say the L-system is generating an IFS itself (i.e., the set of transformations). The formal relationship between IFSs and L-systems is an area of research which could serve as its own section. There are methods of constructing equivalent IFSs out of certain kinds of L-systems [2] (equivalent meaning they each generate the same object), and also methods of expressing certain kinds of IFSs as equivalent L-systems [3]. Because they are quite expressive, perhaps you *could* have an L-system which quite literally generates an IFS. However, I don't think that's what the intro was getting at, as L-system fractal generation is most often written about in the context of Turtle graphics. Druggiero (talk) 02:08, 18 March 2018 (UTC)

Examples...

Example 1 and 2 are practically the same system; having both is somewhat redundant.

Example 3(?) the dust example, should be changed to use conventional notation namely F for draw forward and f for move forward.

Example 5(?) the penrose tilings example, doesn't supply the rules for the system; the rules need to be added or the example scrapped.

All the examples really need reworking; the term 'constants' isn't one that's really used in any of the published papers on L-systems.

The article could use an example of the various common types of L-system, stochastic (random), parametric and context sensitive.

87.194.144.173 (talk) 15:36, 3 May 2010 (UTC)

Cantor example is nothing like the diagram

The rules give:

n = 1 : ABA
n = 2 : ABABBBABA
n = 3 : ABABBBABABBBBBBBBBABABBBABA
n = 4 : ABABBBABABBBBBBBBBABABBBABABBBBBBBBBBBBBBBBBBBBBBBBBBBABABBBABABBBBBBBBBABABBBABA

now only if each line is scaled to the same lenghth might you get something like the picture. --Paddy (talk) 23:33, 14 May 2011 (UTC)

The scaling is so typical, perhaps it was overseen to mention it. The L-system itself is just the evolution of the character strings from one generation to the next. On top of that one may feed the character string of each generation as command sequence into a drawing machine like the (LOGO) Turtle. To obtain convergence of some kind one has to care how the characters relate to commands. This means adjusting the angles and step sizes, and also the orientation of the turtle at the start point, if in 2D. In the Cantor example this is simple -- three times as many characters, each a move forward, means one third of the step size from one generation to the next.--LutzL (talk) 13:19, 15 May 2011 (UTC)

Chomskys "Ultra-conservative" views

Without wanting to make any statement about the facts, could the sentences "yes: in language theory, Chomsky is ultra-conservative" please be reworked or removed? This does not sound very encyclopedia-like. In general, the whole paragraph "Chomsky's conservative...refer to Chomsky.[2]" should probably not in the introduction of the article but maybe at some later point. 95.117.217.100 (talk) 11:24, 25 July 2011 (UTC)

I have removed that paragraph from the article's lead. I am not completely sure what the editor who wrote this was trying to say, but in any case it has no relevance to the subject of this article. Gandalf61 (talk) 11:40, 25 July 2011 (UTC)

Context-free systems

I don't know L-systems so well but in general formal languages the context-free ones are a strictly larger class that the mentioned equivalents of regular languages. It seems to apply here as well. Can someone competent look at it and eventually fix it? Neználek (talk) 13:17, 11 April 2012 (UTC)

See the "subset or superset" talk topic below. 67.198.37.16 (talk) 20:53, 11 February 2024 (UTC)

This Article Needs A ReWrite

As it is now, I can't tell if it's supposed to be about some type of mathematics or what. The article has tons of images of random plants and is talking all about biology and other non-math things. I'm pretty sure the concept of "L-System" is purely mathematical.... please remove these ancillary or tangential "connections" or at least dont make them the focus of the article anymore. — Preceding unsigned comment added by 71.201.95.139 (talk) 21:02, 8 May 2013 (UTC)

L-systems are a mathematical concept that have applications in modelling plants and other organisms. We can't write about L-systems without including these applications. However, I have modified the lead paragraph so that it says what an L-system is before it mentions applications in biology. Gandalf61 (talk) 08:48, 9 May 2013 (UTC)

Edit by RCB I think so too, the article is not precise. Like for example "growth patterns of various types of algae, such as the blue/green bacteria Anabaena catenula." - Algae are NOT BACTERIA! — Preceding unsigned comment added by 62.61.159.141 (talk) 13:38, 22 June 2015 (UTC)

The thing the article is talking about is what is known as Cyanobacteria. One of the common names for cyanobacteria is "blue-green algae". It may be a misnomer, but it is not at odds with common usage. — Preceding unsigned comment added by 2003:69:CD6A:F401:D189:4DF8:E1B0:B7D0 (talk) 11:53, 15 September 2015 (UTC)

It isn't at odds with common use of blue-green algae, but the term algae does not include blue-green algae. Referring to the one as the general case, and the other as a specific case, is plainly wrong. The Real Marauder (talk) 21:18, 18 May 2017 (UTC)

Subset or Superset of Languages

The article states in the "L-system structure" section that "L-systems are strict subsets of languages". Since formal languages are produced by applying only one production rule at a time in each iteration, but L-systems apply all possible matching production rules in each iteration, shouldn't L-systems be considered supersets of languages (or, equivalently, that languages are strict subsets of L-systems)? At present, there is no citation or reference for the subset claim. — Loadmaster (talk) 15:40, 25 October 2016 (UTC)

"Languages", as generally conceived, consist of a collection of production rules (or term rewriting rules, or syntax - syntactical grammar elements) applied at one fixed location in space (usually a nebulous location, such as "inside the computer"). The conventional Chomsky hierarchy applies only to this concept of a language happening only at one location. By contrast, L-systems happen in many physical locations, all at the same time. The idea is that each biological cell contains DNA/RNA that encodes a term rewriting system or some syntax/grammar, and, as that cell, as it lives and grows, expresses that grammar, at the location where that cell is located. This is related to the idea of a cellular automaton as well as to distributed computing.

So far, so good. Now here is the trick: you can take a pencil, and draw a big box around the entire L-system, and say "everything inside of there is happening at one location", and define a "big" language that is the (Cartesian) product of all the "small" individual languages running in each cell. The general theorem is that a Cartesian product of multiple Turing machines (or of finite automata) is no more powerful than a single Turing machine (or finite automaton). Thus, in the conventional Chomsky hierarchy, they are at the same level, the same power. The resulting language is neither a superset nor a subset, but equally expressive.

The above holds true when one is working with a fixed, finite number of automata/turing machines (a finite-dimensional Cartesian product). The only way to evade this conclusion about the expressive power of languages is to take the $n\to \infty$ limit. In this limit things ... work differently. The result of that limit is called a geometric automaton, and the so-called quantum computers are special cases of this. Many people like to imagine that quantum computers are kind-of-like Turing machines with an infinite number of states, but, due to the no-cloning theorem, they can't have tapes, so this is not the correct way to imagine them. The correct concept for the $n\to \infty$ limit of a Turing machine is of the automorphism group of a homogeneous space. The symbols/rewrite terms/grammar are just the rules that generate sequences of automorphisms that are to be applied to the space. The stopping function ("this computation has run to it's conclusion and the machine has halted and here is the answer: its 42") is an integral over a measure defined by the Borel sigma algebra over the space (you cannot use the Lesbesgue measure for this, because it is complete; see for example, abstract Wiener space for why this is a problem.) These types of systems do not fit cleanly into the conventional Chomsky hierarchy, and the computational expressive power of such systems is poorly understood. This is an active area of research, it goes under the name of descriptive set theory, where the properties of the (bold-face) Borel hierarchy are studied.

The above is the general sketch. I don't know of any existing wikipedia article that recaps what I wrote above. Most of what I wrote above was figured out in the 1980's, 1990's by the dynamical systems people, and is so is called "well-known" by the people who know it. But I don't know any central or seminal book or journal or "theory" that encompasses this; its sort-of scattershot and spread all about the journals. I guess maybe work on sofic shifts (shift spaces) is about as central as it gets, but that has only a poor overlap with the descriptive set theory. The quantum computing people mostly kind-of ignore all this, anyway. The reason they ignore this is ergodicity aka "noise": if you just apply a bunch of automorphisms to some homogeneous space, you will typically get a washed-out mess, aka "thermalization". The quantum computing people struggle to not thermalize. There's no way for them to move "up" the Borel hierarchy. This is kind of why L-systems are interesting: if you stick each system into a bottle, (vacuum bottle, thermos bottle) where outside forces cannot screw up the internal state, then you can perform significant and meaningful computations. This is the magic of the bilipid layer in biological cells: it isolates the inside of the cell from the external world, allowing the ribosomes and the DNA to do their thing. However, given the "origins of life" debate, and the autopoiesis hoo-haa, no one really understands how this kind of isolation actually works. Nothing in ergodic theory or thermodynamics tells you how to do that, in a formal rigorous proof-theory mathematical sense. L-systems is one of the more solid approaches that we have, right now, to that particular problem. This article is mostly a pop-sci description of L-systems; it ignores formal work. 67.198.37.16 (talk) 20:46, 11 February 2024 (UTC)

Angle Used for Koch curve

Should be 60 degrees not 90 degrees. Flaviusvulso (talk) 19:25, 24 March 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on L-system. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20020503212834/http://spanky.triumf.ca/WWW/FRACTINT/lsys/truefractal.html to http://spanky.triumf.ca/www/fractint/lsys/truefractal.html
• Added archive https://web.archive.org/web/20031220074045/http://www.generation5.org/content/2002/lse.asp to http://www.generation5.org/content/2002/lse.asp

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 22:01, 25 May 2017 (UTC)

Hilbert curve example

Hi, the Hilbert_curve#Representation_as_Lindenmayer_system is not so didactic as here, can you add the Hilbert curve (in a more didactic steps) as more one example?

Open Problems - L-system inference

One of the open problems listed is given a structure find the L-system that creates it. This is no longer an open problem. The work by Jason Bernard (me) and Ian McQuillan largely solved this between 2016 and 2020. Deterministic, stochastic, and parametric L-systems can all be easily inferred from a structure (sequence of strings). Context-sensitive was found to have a negligible effect on inference difficulty. We also have another paper coming out soon on inferring homomorphic L-systems.

My dissertation (which has pretty much everything): Bernard, J. (2020). Inferring Different Types of Lindenmayer Systems Using Artificial Intelligence (Doctoral dissertation, University of Saskatchewan).

For deterministic L-systems: Jason Bernard, Ian McQuillan, Techniques for inferring context-free Lindenmayer systems with genetic algorithm, Swarm and Evolutionary Computation, Volume 64, 2021, 100893, ISSN 2210-6502, https://doi.org/10.1016/j.swevo.2021.100893

For stochastic L-systems: Bernard, J., McQuillan, I. Stochastic L-system inference from multiple string sequence inputs. Soft Comput 27, 6783–6798 (2023). https://doi.org/10.1007/s00500-022-07683-8

For parametric L-systems: J. Bernard and I. McQuillan, "Inferring Temporal Parametric L-systems Using Cartesian Genetic Programming," 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), Baltimore, MD, USA, 2020, pp. 580-588, doi: 10.1109/ICTAI50040.2020.00095.

For context-sensitivity: McQuillan, I., Bernard, J., Prusinkiewicz, P. (2018). Algorithms for Inferring Context-Sensitive L-Systems. In: Stepney, S., Verlan, S. (eds) Unconventional Computation and Natural Computation. UCNC 2018. Lecture Notes in Computer Science(), vol 10867. Springer, Cham. https://doi.org/10.1007/978-3-319-92435-9_9 50.100.214.247 (talk) 02:59, 25 November 2024 (UTC)