L-sistem

Drevesa L-sistema tvorijo realistične modele naravnih vzorcev

L-sistem ali Lindenmayerjev sistem je vzporedni sistem prepisovanja in vrsta formalne slovnice. L-sistem sestavlja abeceda simbolov, ki se lahko uporabijo za ustvarjanje znakovnih nizov (stringov), zbirke produkcijskih pravil, ki vsak simbol razširijo v nek večji znakovni niz simbolov, začetnega »aksiomskega« znakovnega niza, iz katerega se začne konstrukcija, in mehanizma za prevajanje ustvarjenih znakovnih nizov v geometrijske strukture. L-sisteme je leta 1968 predstavil in razvil Aristid Lindenmayer, madžarski teoretični biolog in botanik na Univerzi v Utrechtu. L-sisteme je uporabil za opis vedenja rastlinskih celic in za modeliranje rastnih procesov razvoja rastlin. L-sistemi so bili uporabljeni tudi za modeliranje morfologije različnih organizmov in se lahko uporabljajo za ustvarjanje samopodobnih fraktalov.

Izvori

Predstavitve rastlin, ustvarjene z uporabo L-sistema v treh razsežnostih.

Kot biolog se je Lindenmayer ukvarjal s kvasovkami in nitastimi glivami ter preučeval vzorce rasti različnih vrst bakterij, kot je modrozelena cepljivka (cianobakterija) Anabaena catenula. Prvotno so bili L-sistemi zasnovani za formalni opis razvoja takšnih preprostih večceličnih organizmov in za ponazoritev sosedskih odnosov med rastlinskimi celicami. Kasneje je bil ta sistem razširjen na opis višjih rastlin in kompleksnih razvejanih struktur.

Struktura L-sistema

Rekurzivna narava pravil L-sistema vodi do samopodobnosti, zato je fraktalne oblike enostavno opisati z L-sistemom. Rastlinske modele in organske oblike naravnega videza je enostavno definirati, saj z naraščanjem ravni rekurzije oblika počasi 'raste' in postaja kompleksnejša. Lindenmayerjevi sistemi so priljubljeni tudi pri ustvarjanju umetnega življenja.

Slovnice L-sistemov so zelo podobne slovnici polThuejevi slovnici (glej hierarhija Chomskega). L-sistemi so sedaj splošno znani kot parametrični L-sistemi, definirani kot trojica.

$\mathbf {G} =(V,\omega ,P)\!\,,$

kjer je:

• $\mathbf {V} \!\,$ – (abeceda) množica simbolov, ki vsebuje tako elemente, ki jih je mogoče nadomestiti (spremenljivke), kot tiste, ki jih ni mogoče nadomestiti (konstante ali terminali)
• ${\boldsymbol {\omega }}\!\,$ – (začetek, aksiom ali iniciator) je znakovni niz simbolov iz $\mathbf {V} \!\,$, ki definira začetno stanje sistema
• $\mathbf {P} \!\,$ – množica produkcijskih pravil ali produkcij, ki definira način na katerega se lahko spremenljivke zamenjajo s kombinacijamiu konstant in drugih spremenljivk. Produkcijo sestavljata dva znakovna niza, predhodnik in naslednik. Za poljubni $A\!\,$, ki je element množice $V\!\,$ in se ne pojavlja na levi strani produkcije v $P\!\,$, se predpostavlja identična produkcija $A\to A\!\,$ – ti simboli se imenujejo konstante ali terminali. (Glej zakon identičnosti).

Pravila slovnice L-sistema se uporabljajo iterativno, začenši od začetnega stanja. Na iteracijo se hkrati uporabi čim več pravil. Dejstvo, da vsaka iteracija uporabi čim več pravil, razlikuje L-sistem od formalnega jezika, nastalega iz formalne slovnice, ki na iteracijo uporabi le eno pravilo. Če bi se produkcijska pravila uporabljala le eno naenkrat, bi se preprosto ustvarilo znakovni niz v jeziku in vsa taka zaporedja aplikacij bi ustvarila jezik, ki ga določa slovnica. Vendar pa v nekaterih jezikih obstajajo znakovni nizi, ki jih ni mogoče ustvariti, če se slovnico obravnava kot L-sistem in ne kot jezikovno specifikacijo. Na primer, naj se predpostavi, da v slovnici obstaja pravilo $S\to SS\!\,$. Če se produkcije izvajajo ena naenkrat, potem se lahko, začenši s $S\!\,$, najprej dobi $SS\!\,$ in nato, če se pravilo ponovno uporabi, $SSS\!\,$. Če pa se uporabijo vsa ustrezna pravila v vsakem koraku, kot v L-sistemu, potem se ne da dobiti te stavčne oblike. Namesto tega bi prvi korak dal $SS\!\,$, drugi pa bi pravilo uporabil dvakrat, kar bi dalo $SSSS\!\,$. Tako je množica znakovnih nizov, ustvarjena z L-sistemi iz dane slovnice, podmnožica formalnega jezika, ki ga definira slovnica, in če se jezik definira kot množico znakovnih nizov, to pomeni, da je dani L-sistem dejansko podmnožica formalnega jezika, ki ga definira slovnica L-sistema.

L-sistem je kontekstno prost, če se vsako produkcijsko pravilo nanaša le na posamezen simbol in ne na njegove sosede. Kontekstno prosti L-sistem je torej določen s kontekstno prosto slovnico. Če pravilo ni odvisno le od enega samega simbola, temveč tudi od njegovih sosedov, se imenuje kontekstno občutljivi L-sistem.

Če obstaja natanko ena produkcija za vsak simbol, potem je L-sistem determinističen (deterministični kontekstno prosti L-sistem se popularno imenuje sistem D0L). Če jih je več in je vsak izbran z določeno verjetnostjo med vsako iteracijo, potem gre za stohastični L-sistem.

Uporaba L-sistemov za ustvarjanje grafičnih slik zahteva, da se simboli v modelu nanašajo na elemente risbe na računalniškem zaslonu. Program Fractint na primer uporablja želvjo grafiko (podobno tisti v programskem jeziku Logo) za ustvarjanje slik na zaslonu. Vsako konstanto v modelu L-sistema interpretira kot želvin ukaz.

Zgledi L-sistemov

Zgled 1: alge

Lindenmayerjev izvirni L-sistem za modeliranje rasti alg.

spremenljivke : A, B

konstante : nobena

aksiom : A

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

kar ustvari:

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : ABAABABA

n = 5 : ABAABABAABAAB

n = 6 : ABAABABAABAABABAABABA

n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Zgled 1: alge, s pojasnili

n = 0:             A             začetek (aksiom/iniciator)
                  / \
n = 1:           A   B           začetni A postane AB s pravilom (A → AB), pravilo (B → A) se ne da uporabiti
                /|     \
n = 2:         A B      A        prejšnji znakovni niz AB z vsemi uporabljenimi pravili, A je spet postal AB,
prejšnji B se je spremenil v A
             / | |       | \
n = 3:       A B A       A B     upošteva se, da vsi A najprej ustvarijo kopijo sebe, nato pa B, ki se spremeni ...
           / | | | \     | \ \
n = 4:     A B A A B     A B A   ... v A eno generacijo kasneje in se nato začne pojavljati/ponavljati/rekurzivno pojavljati

Rezultat je zaporedje Fibonaccijevih besed. Če se šteje dolžino vsakega znakovnega niza, se dobi Fibonaccijevo zaporedje števil (pri čemer se prva 1 preskoči zaradi izbire aksioma):

1 2 3 5 8 13 21 34 55 89 ...

Če se ne želi preskočiti prve 1, se lahko uporabi aksiom $B\!\,$. To bi postavilo vozlišče $B\!\,$ pred najvišje vozlišče ($A\!\,$) zgornjega grafa.

Za vsak znakovni niz, če se šteje $k\!\,$-ti položaj od levega konca znakovnega niza, je vrednost določena s tem, ali mnogokratnik zlatega reza spada v interval $(k-1,k)\!\,$. Razmerje med $A\!\,$ in $B\!\,$ prav tako konvergira k zlatemu rezu.

Ta zgled daje enak rezultat (glede dolžine vsakega znakovnega niza, ne zaporedja $A\!\,$jev in $B\!\,$jev), če se pravilo ($A\to AB\!\,$) nadomesti z ($A\to BA\!\,$), le da so znakovni nizi zrcaljeni.

To zaporedje je krajevno katenativno, ker je $G(n)=G(n-1)G(n-2)\!\,$, kjer je $G(n)\!\,$ $n\!\,$-ta generacija.

Zgled 2: fraktalno (dvojiško) drevo

• spremenljivke : 0, 1
• konstante: »[«, »]«
• aksiom : 0
• pravila : (1 → 11), (0 → 1[0]0)

Oblika dvojiškega drevesa se gradi z rekurzivnim podajanjem aksioma skozi produkcijska pravila. Vsak znak vhodnega znakovnega niza se preveri s seznamom pravil, da se določi, s katerim znakom ali znakovnim nizom ga je treba nadomestiti v izhodnem znakovnem nizu. V tem primeru '1' v vhodnem znakovnem nizu postane '11' v izhodnem znakovnem nizu, medtem ko '[' ostane enak. Če se to uporabi za aksiom '0', nastane:

aksiom:	0
1. rekurzija:	1[0]0
2. rekurzija:	11[1[0]0]1[0]0
3. rekurzija:	1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
...

Vidi se lahko, da ta znakovni niz hitro raste v velikosti in kompleksnosti. Ta znakovni niz se lahko nariše kot sliko z uporabo želvje grafike, kjer je vsakemu simbolu dodeljena grafična operacija, ki jo mora želva izvesti. V zgornjem primeru lahko na primer želva dobi naslednja navodila:

• 0: risanje daljice, ki se konča v listu
• 1: risanje daljice
• [: postavljanje (push) lege in kota, zavijanje levo za 45°
• ]: vzemanje (pop) lege in kota, zavijanje desno za 45°

Postavljanje in vzemanje se nanašata na sklad LIFO (bolj tehnična slovnica bi imela ločena simbola za »postavljanje lege« in »zavijanje levo«). Ko interpretacija želve naleti na '[', se trenutni lega in kot shranita, nato pa se obnovita, ko interpretacija naleti na ']'. Če je bilo »postavljenih« več vrednosti, potem »vzemanje« obnovi nazadnje shranjene vrednosti. Če se zgoraj navedena grafična pravila uporabi za prejšnjo rekurzijo, nastane:

• 
  Aksiom
• 
  1. rekurzija
• 
  2. rekurzija
• 
  3. rekurzija
• 
  4. rekurzija
• 
  7. rekurzija, desetkrat zmanjšana

Zgled 3: Cantorjeva množica

spremenljivke : A, B

konstante : nobena

začetek : A {začetni znak znakovnega niza}

pravila : (A → ABA), (B → BBB)

Naj A pomeni »risanje naprej« in B »premikanje naprej«.

Tako nastane znana Cantorjeva množica na realni osi $\mathbb {R} \!\,$.

Zgled 4: Kochova krivulja

Različica Kochove krivulje, ki uporablja le prave kote.

spremenljivke : F

konstante : +, −

začetek : F

pravila : (F → F+F−F−F+F)

Tukaj F pomeni »risanje naprej«, + »zavijanje levo za 90°« in − »zavijanje desno za 90°« (glej želvja grafika).

n = 0:

F

n = 1:

F+F−F−F+F

n = 2:

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

n = 3:

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F−

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F−

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

Zgled 5: trikotnik Sierpińskega

Trikotnik Sierpińskega ustvarjen s pomočjo L-sistema.

spremenljivke : F, G

konstante : +, −

začetek : F−G−G

pravila : (F → F−G+F+G−F), (G → GG)

kot : 120°

Tukaj F in G obe pomenita »risanje naprej«, + »zavijanje levo za kot« in − »zavijanje desno za kot«.

• 
  $n=2\!\,$
• 
  $n=4\!\,$
• 
  $n=6\!\,$

Trikotnik Sierpińskega je mogoče aproksimirati tudi z uporabo L-sistema krivulje puščične konice Sierpińskega.

spremenljivke : A, B

konstante : +, −

začetek : A

pravila : (A → B−A−B), (B → A+B+A)

kot : 60°

Tukaj A in B obe pomenita »risanje naprej«, + »zavijanje levo za kot« in − »zavijanje desno za kot« (glej želvja grafika).

Razvoj za $n=2\!\,$, $n=4\!\,$, $n=6\!\,$ in $n=8\!\,$

Zgled 6: zmajeva krivulja

Zmajeva krivulja ustvarjena s pomočjo L-sistema.

spremenljivke : F, G

konstante : +, −

začetek : F

pravila : (F → F+G), (G → F−G)

kot : 90°

Tukaj F in G obe pomenita »risanje naprej«, + »zavijanje levo za kot« in − »zavijanje desno za kot«.

n = 0 : F

n = 2 : F+G

n = 2 : F+G+F−G

n = 3 : F+G+F−G+F+G−F−G

n = 4 : F+G+F−G+F+G−F−G+F+G+F−G−F+G−F−G

Zmajeva krivulja za $n=10\!\,$

Zgled 7: fraktalna rastlina

Glej tudi: Barnsleyjeva praprot

spremenljivke : X, F

constants : +, −, »[«, »]«

začetek : −X

pravila : (X → F+[[X]−X]−F[−FX]+X), (F → FF)

kot : 25°

Najprej je treba inicializirati prazen sklad. To sledi metodi LIFO (zadnji noter, prvi ven) za dodajanje in odstranjevanje elementov. Tukaj F pomeni »risanje naprej«, − »zavijanje desno za 25°« in + »zavijanje levo za 25°«. X ne ustreza nobenemu dejanju risanja in se uporablja za nadzor razvoja krivulje. Oglati oklepaj »[« ustreza shranjevanju trenutnih vrednosti za lego in kot, zato se lega in kot postavita na vrh sklada. Ko se naleti na znak »]«, se s sklada vzame in lega ter kot se ponastavita. Vsak »[« je pred vsakim znakom »]«.

Fraktalna rastlina za $n=6\!\,$

Različice

Razvitih je bilo več podrobnih opisov te osnovne tehnike L-sistemov, ki jih je mogoče uporabljati skupaj. Med njimi so stohastične slovnice, kontekstno občutljive slovnice in parametrične slovnice.

Stohastične slovnice

Slovnični model, o katerem je bilo do sedaj govora, je bil determinističen – to pomeni, da za vsak simbol v slovnični abecedi obstaja natanko eno produkcijsko pravilo, ki je vedno izbrano in vedno izvede isto pretvorbo. Ena od možnosti je, da se za simbol določi več kot eno produkcijsko pravilo, pri čemer se vsakemu določi verjetnost, da se pojavi. Na primer, v slovnici zgleda 2 bi se lahko spremenilo pravilo za prepisovanje »0« iz:

0 → 1[0]0

v verjetnostno pravilo:

0 (0,5) → 1[0]0

0 (0,5) → 0

Pri tej produkciji, kadar bi se med prepisovanjem znakovnega niza srečal znak »0«, bi obstajala 50-odstotna verjetnost, da bi se obnašala, kot je bilo opisano prej, in 50-odstotna verjetnost, da se med produkcijo ne bi spremenila. Ko se stohastična slovnica uporablja v evolucijskem kontekstu, je priporočljivo v genotip vključiti naključno seme, tako da stohastične značilnosti slike ostanejo nespremenjene med generacijami.

Kontekstno občutljive slovnice

Kontekstno občutljivo produkcijsko pravilo ne upošteva le simbola, ki ga spreminja, temveč tudi simbole v znakovnem nizu, ki se pojavljajo pred njim in za njim. Na primer, produkcijsko pravilo:

b < a > c → aa

transformira »a« v »aa«, vendar samo, če se »a« pojavi med »b« in »c« v vhodnem znakovnem nizu:

...bac...

Kot pri stohastičnih produkcijah obstaja več produkcij za obravnavo simbolov v različnih kontekstih. Če za dani kontekst ni mogoče najti produkcijskega pravila, se predpostavlja identitetna produkcija in simbol se pri transformaciji ne spremeni. Če znotraj iste slovnice obstajata tako kontekstno občutljiva kot kontekstno prosta produkcija, se predpostavlja, da ima kontekstno občutljiva produkcija prednost, kadar je uporabna.

Parametrične slovnice

V parametrični slovnici ima vsak simbol v abecedi seznam parametrov, ki je z njim povezan. Simbol, povezan s seznamom parametrov, se imenuje modul, znakovni niz v parametrični slovnici pa je vrsta modulov. Zgled znakovnega niza je lahko:

a(0, 1)[b(0, 0)]a(1, 2)

Parametre lahko uporabljajo funkcije risanja in tudi produkcijska pravila. Produkcijska pravila lahko parametre uporabljajo na dva načina: prvič, v pogojnem stavku, ki določa, ali bo pravilo veljalo, in drugič, produkcijsko pravilo lahko spremeni dejanske parametre. Na primer pri:

a(x, y) : x == 0 → a(1, y + 1)b(2, 3)

Modul a(x, y) se po tem produkcijskem pravilu transformira, če je izpolnjen pogoj x = 0. Na primer, a(0, 2) bi se transformiral, a(1, 2) pa ne.

V transformacijskem delu produkcijskega pravila se lahko vpliva tako na parametre kot na celotne module. V zgornjem zgledu je znakovnemu nizu dodan modul b(x, y) z začetnimi parametri (2, 3). Prav tako se transformirajo parametri že obstoječega modula. V skladu z zgornjim produkcijskim pravilom:

a(0, 2)

postane:

a(1, 3)b(2, 3),

ker se parameter »x« od a(x, y) eksplicitno transformira v »1«, parameter »y« od a pa se poveča za ena.

Parametrične slovnice omogočajo, da dolžine črt in kote razvejanja določi slovnica in ne metode želvje interpretacije. Če je podana tudi starost kot parameter za modul, se lahko pravila spreminjajo glede na starost rastlinskega segmenta, kar omogoča ustvarjanje animacij celotnega življenjskega cikla drevesa.

Dvosmerne slovnice

Dvosmerni model eksplicitno ločuje sistem simbolnega prepisovanja od dodeljevanja oblik. Na primer, postopek prepisovanja znakovnih nizov v zgledu 2 (fraktalno (dvojiško) drevo) je neodvisen od tega, kako so grafične operacije dodeljene simbolom. Z drugimi besedami, za dani sistem prepisovanja je uporabno neskončno število metod risanja.

Dvosmerni model je sestavljen iz 1) procesa naprej, ki gradi drevo izpeljave s produkcijskimi pravili, in 2) procesa nazaj, ki drevo z oblikami realizira postopno (od listov do korena). Vsak korak inverzne izpeljave vključuje bistveno geometrijskotopološko sklepanje. S tem dvosmernim ogrodjem so oblikovne omejitve in cilji kodirani v prevodu slovnice in oblike. V aplikacijah arhitekturnega oblikovanja ima dvosmerna slovnica dosledno notranjo povezljivost in bogato prostorsko hierarhijo.

Konstrukcija in inferenčnost L-sistema

Ročna konstrukcija L-sistema

Zgodovinsko gledano je bila konstrukcija L-sistemov močno odvisna od ročnega dela strokovnjakov, kar je zahtevalo podrobne meritve, poznavanje področja in znatne časovne naložbe. Postopek je pogosto vključeval analizo bioloških struktur in kodiranje njihovih razvojnih pravil v L-sisteme, simbol za simbolom. Zaradi te delovno intenzivne metode je bilo ustvarjanje natančnih modelov za kompleksne procese dolgočasno in nagnjeno k napakam.

Pomemben primer je Nishidovo delo na japonskih cipresah (Chamaecyparis obtusa), kjer je ročno segmentiral veje iz niza slik in identificiral 42 različnih mehanizmov rasti za konstrukcijo stohastičnega L-sistema. Kljub znatnemu vloženemu trudu je nastali sistem zagotovil le približek rasti drevesa, kar ponazarja izzive ročnega kodiranja tako podrobnih bioloških procesov. Ta naporna naloga je bila opisana kot »mučna in zapletena«, kar je poudarilo omejitve ročnih pristopov.

Izzivi ročne konstrukcije L-sistemov so dobro dokumentirani tudi v knjigi Algoritemska lepota rastlin (The Algorithmic Beauty of Plants) avtorjev Przemysława Prusinkiewicza in Lindenmayerja. Knjiga prikazuje, kako lahko L-sistemi elegantno modelirajo rast rastlin in fraktalne vzorce, vendar so primeri pogosto zahtevali posredovanje strokovnjakov za opredelitev potrebnih pravil.

Ročno konstrukcijo je dodatno omejevala potreba po specifičnem strokovnem znanju, kot je razvidno iz drugih aplikacij L-sistemov, ki presegajo biologijo, kot sta arhitekturno načrtovanje in urbanistično modeliranje. Na teh področjih je ustvarjanje natančnega L-sistema zahtevalo ne le razumevanje formalizma L-sistema, temveč tudi obsežno poznavanje modelirane domene.

Inferenčnost L-sistema

Zamisel o avtomatizaciji inferenčnosti (sklepanju) L-sistemov se je pojavila, da bi odpravila neučinkovitost ročnih metod, ki so pogosto zahtevale obsežno strokovno znanje, meritve in postopke poskusov in napak. Namen te avtomatizacije je bil omogočiti inferenčnost L-sistemov neposredno iz opazovalnih podatkov, s čimer bi se odpravila potreba po ročnem kodiranju pravil.

Začetni algoritmi so bili primarno usmerjeni na deterministične kontekstno proste L-sisteme (sisteme D0L), ki spadajo med najpreprostejše vrste L-sistemov. Ta zgodnja prizadevanja so pokazala izvedljivost samodejne inferenčnosti, vendar so bila po obsegu zelo omejena, saj so običajno obravnavala le sisteme z majhnimi abecedami in preprostimi pravili prepisovanja. Nakanovo delo je na primer poudarilo izzive inferenčnosti L-sistemov z večjimi abecedami in kompleksnejšimi strukturami, nalogo pa je opisalo kot »izjemno zapleteno«.

Ročna in polavtomatska orodja

Zgodnja orodja za inferenčnost L-sistemov so bila pogosto zasnovana tako, da pomagajo strokovnjakom, ne pa da bi jih nadomestila. Sistemi, ki so uporabniku predstavili populacijo potencialnih L-sistemov in mu omogočili izbiro estetsko prijetnih ali verjetnih možnosti, so na primer zmanjšali del ročnega bremena. Vendar so se ta orodja močno zanašala na človeško presojo in niso v celoti avtomatizirala procesa inferenčnosti.

Pristopi inferenčnosti, specifični za domeno

Nekateri zgodnji algoritmi so bili tesno integrirani v specifična raziskovalna področja, predvsem modeliranje rastlin. Ti pristopi so uporabljali domensko znanje za omejitev iskalnega prostora in doseganje boljših rezultatov. Vendar pa je njihova odvisnost od vnaprej določenih domensko specifičnih pravil omejevala njihovo posplošljivost in uporabnost na druga področja.

Posplošeni algoritmi inferenčnosti

Poskusi ustvarjanja posplošenih algoritmov za inferenčnost L-sistemov so se začeli z determinističnimi kontekstno prostimi sistemi. Raziskovalci so želeli inferirati na L-sisteme zgolj iz podatkov, kot so zaporedja znakovnih nizov ali časovni podatki iz slik, ne da bi se zanašali na specifično znanje o domeni. Ti algoritmi so naleteli na znatne izzive, vključno z:

• eksponentno rastjo iskalnega prostora z naraščajočo velikostjo abecede in kompleksnostjo pravil.
• obravnavo nepopolnih ali šumnih podatkov, ki so v inferenčne sisteme vnesli napake.
• omejitvami računske učinkovitosti, saj so izčrpne metode iskanja postale neobvladljive za vse razen za najpreprostejše primere.

Bernardova doktorska disertacija, ki jo je mentoriral Ian McQuillan na Univerzi Saskatchewana, predstavlja pomemben napredek pri interferenčnosti L-sistemov, saj uvaja paket orodij za interferenčnost modelov rastlin (PMIT). Kljub imenu je to orodje neodvisno od problema in je tako poimenovano zaradi vira prvotnega financiranja projekta P2IRC. Ta orodja obravnavajo izzive interferenčnosti determinističnih, stohastičnih in parametričnih L-sistemov:

Deterministični kontekstno prosti L-sistemi (D0L):

Orodje PMIT-D0L je izboljšalo najsodobnejšo tehnologijo, saj je omogočilo inferenčnost L-sistemov z do 31 simboli v primerjavi s prejšnjimi algoritmi, ki so upravljali le z dvema. To je bilo doseženo z novimi tehnikami kodiranja in metodami za zmanjšanje iskalnega prostora.

Deterministični kontekstno občutljivi L-sistemi (D(j,k)L):

Orodje PMIT-DCSL je dodatno izboljšalo inferenčnost determinističnih L-sistemov z dokazovanjem, da tehnike delujejo v kontekstualno občutljivem primeru z majhnimi spremembami. To orodje je predstavilo tudi nadaljnje izboljšave, ki omogočajo inferenčnost determinističnih L-sistemov z do stotinami simbolov. Poleg tega to delo in McQuillanov teoretični članek dokazujeta kompleksnost inferenčnosti kontekstualno občutljivih L-sistemov. V neobjavljenem delu Bernard trdi, da dokazuje, da kontekstualna občutljivost nikoli ne spremeni temeljne narave problema inferenčnosti, ne glede na pravilo izbora. To pomeni, da je inferenčnost kontekstualno občutljivih stohastičnih L-sistemov mogoča, če je mogoča inferenčnost kontekstno prostega L-sistema.

Stohastični L-sistemi (S0L):

Za stohastične L-sisteme je bilo razvito orodje PMIT-S0L, ki uporablja hibridni pristop pohlepnega in genetskega algoritma za inferenčnost o sistemih iz več zaporedij znakovnih nizov. Orodje je pokazalo sposobnost inferenčnosti o pravilih prepisovanja in verjetnostih z visoko natančnostjo, kar je prvo na tem področju.

Časovni parametrični L-sistemi:

McQuillan je prvi ugotovil, da se lahko parametrične L-sisteme predstavlja kot stohastične L-sisteme — vendar to ni rešilo problema inferenčnosti o parametričnih izbirnih pravilih. Z uporabo kartezičnega genetskega programiranja je bilo mogoče sklepati o parametričnih L-sistemih skupaj s parametričnimi izbirnimi pravili, če je nabor parametrov vključeval čas (da bi zagotovili zaporedje parametrov, vendar je čas razumen parameter za vsak resnični proces). To orodje, PMIT-PARAM, je uspešno inferiralo o kompleksnih sistemih z do 27-imi pravili prepisovanja, s čimer je postavilo nov standard v inferenčnosti o L-sistemih.

Odprti problemi

Pri preučevanju L-sistemov je veliko odprtih problemov. Na primer:

• karakterizacija vseh determinističnih kontekstno prostih L-sistemov, ki so krajevno katenativni. (Popolna rešitev je znana le v primeru, ko obstajata le dve spremenljivki).

Vrste L-sistemov

L-sistem na realni osi $\mathbb {R} \!\,$ je na primer:

• Prouhet-Thue-Morsejev sistem

Znani L-sistemi na ravnini $\mathbb {R} ^{2}\!\,$ so:

• krivulje zapolnjevanja prostora (Hilbertova krivulja, Peanove krivulje, Dekkingova cerkev, kolami),
• medianske krivulje zapolnjevanja prostora (Lévyjeva krivulja C, Harter-Heighwayeva zmajeva krivulja, Davis-Knuthova trojna zmajeva krivulja),
• pokritja (sfingino pokritje, Penroseovo pokritje)

Glej tudi

• digitalna morfogeneza
• sistem iterirane funkcije (IFS)
• reakcijskodifuzijski sistem – vrsta matematičnega modela, ki zagotavlja simulacije difuzijskih kemičnih reagentov (vključno s simulacijami, podobnimi realističnim)
• verjetnostna kontekstno prosta slovnica
• The Algorithmic Beauty of Plants

Viri

• Anastacio, Fabricio; Prusinkiewicz, Przemysław; Sousa, Mario Costa (2009), »Sketch-based parameterization of L-systems using illustration-inspired construction lines and depth modulation«, Computers & Graphics, 33 (4): 440–451, doi:10.1016/j.cag.2009.05.001, ISSN 0097-8493
• Bernard, Jason (2020). Inferring Different Types of Lindenmayer Systems Using Artificial Intelligence (PDF) (doktorska disertacija). Univerza Saskatchewana.
• Boudon, Frédéric; Pradal, Christophe; Cokelaer, Thomas; Prusinkiewicz, Przemyslaw; Godin, Christophe (2012), »L-Py: An L-System Simulation Framework for Modeling Plant Architecture Development Based on a Dynamic Language«, Frontiers in Plant Science, 3: 76, Bibcode:2012FrPS....3...76B, doi:10.3389/fpls.2012.00076, ISSN 1664-462X, PMC 3362793, PMID 22670147
• Burry, Jane; Burry, Mark (2010), The New Mathematics of Architecture, New York: Thames and Hudson, COBISS 2600068, ISBN 978-0-500-34264-0, OCLC 601096140
• Curry, Roger (2000), On the evolution of parametric L-systems. Technical report, Univerza v Calgaryju
• de la Higuera, Colin (september 2005), »A bibliographical study of grammatical inference.«, Pattern Recognition, 38 (9): 1332–1348, doi:10.1016/j.patcog.2005.01.003, ISSN 0031-3203
• Doucet, P. G. (1974), »The syntactic inference problem for D0L-sequences«, v Rozenberg, Grzegorz; Salomaa, Arto (ur.), L Systems, (Lecture Notes in Computer Science), vol. 15, Berlin, Heidelberg: Springer, str. 146–161, doi:10.1007/3-540-06867-8_12, ISSN 0302-9743
• Ebert, David S.; Musgrave, Kenton F.; Peachey, Darwyn; Perlin, Ken; Worley, Steven (1998), Texturing and Modeling: A Procedural Approach (2. izd.), Elsevier Science & Technology, COBISS 4726038, ISBN 978-0-12-228730-5, OCLC 39189999
• Frijters, Dinnus; Lindenmayer, Aristid (1974), »A model for the growth and flowering of Aster novae-angliae on the basis of table < 1, 0 > L-systems«, v Rozenberg, Grzegorz; Salomaa, Arto (ur.), L systems, (Lecture Notes in Computer Science), vol. 15, Berlin, Heidelberg: Springer, str. 24–52, doi:10.1007/3-540-06867-8_2, ISSN 0302-9743
• Hua, Hao (december 2017), »A Bi‐Directional Procedural Model for Architectural Design« (PDF), Computer Graphics Forum, 36 (8): 219–231, doi:10.1111/cgf.13074, ISSN 0167-7055
• Jennings, Christopher G., »Lindenmayer systems«, cgjennings.ca (v angleščini), pridobljeno 10. julija 2025
• Kari, Lila; Rozenberg, Grzegorz; Salomaa, Arto (1997), »L systems«, v Rozenberg, Grzegorz; Salomaa, Arto (ur.), Handbook of Formal Languages, Berlin, Heidelberg: Springer, str. 253–328, doi:10.1007/978-3-642-59136-5_5, ISBN 978-3-642-63863-3, OCLC 844344227
• Lindenmayer, Aristid (marec 1968), »Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs«, Journal of Theoretical Biology, 18 (3): 300–315, Bibcode:1968JThBi..18..300L, doi:10.1016/0022-5193(68)90080-5, ISSN 0022-5193, PMID 5659072
• McQuillan, Ian; Bernard, Jason; Prusinkiewicz, Przemysław (2018), »Algorithms for Inferring Context-Sensitive L-Systems«, Unconventional Computation and Natural Computation: 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, Proceedings 17, Springer International Publishing, str. 117–130, doi:10.1007/978-3-319-92435-9_9
• Muller, Pascal; Wonka, Peter; Haegler, Simon; Ulmer, Andreas; Van Gool, Luc (2006), »Procedural modeling of buildings«, ACM Transactions On Graphics, 25 (3): 614–623, ISSN 0730-0301
• Nakano, Ryohei (2014), »Emergent induction of deterministic context-free L-system grammar«, Innovations in Bio-inspired Computing and Applications, Springer International Publishing, str. 75–84
• Nishida, Taishin (1980), »K0L-System Simulating Almost but not Exactly the Same Development–Case of Japanese Cypress«, Memoirs of the Faculty of Science, Kyoto University, Series B, 8 (1): 97–122, ISSN 0454-7802
• Pradal, Christophe; Fournier, Christian; Valduriez, Patrick; Cohen-Boulakia, Sarah (2015), »OpenAlea«, Proceedings of the 27th International Conference on Scientific and Statistical Database Management (PDF), str. 1–6, doi:10.1145/2791347.2791365, ISBN 978-1-450-33709-0, S2CID 14246115, arhivirano (PDF) iz spletišča dne 17. oktobra 2019
• Prusinkiewicz, Przemysław; Lindenmayer, Aristid (2012), The Algorithmic Beauty of Plants, Springer Science & Business Media,
  • prostodostopna različica PDF. Arhivirano 2021-04-10 na Wayback Machine.
• Rozenberg, Grzegorz; Salomaa, Arto (1980), The mathematical theory of L systems, New York: Academic Press, COBISS 7960921, ISBN 978-0-125-97140-9, OCLC 5777125
• Rozenberg, Grzegorz; Salomaa, Arto (1992), Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, Berlin, Heidelberg: Springer, ISBN 978-3-540-55320-5, LCCN 92014822, OCLC 25916719
• Runqiang, Bian; Chen, Phoebe; Burrage, Kevin; Hanan, Jim; Room, Peter; Belward, John (2002), »Derivation of L-system models from measurements of biological branching structures using genetic algorithms«, Proceedings of the International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, Springer, str. 514–524

Zunanje povezave

• »Algorithmic Botany«, algorithmicbotany.org (v angleščini), Univerza v Calgaryju
• »Lindenmayer Systems«, rue-a.github.io (v angleščini) – uporabniku prijazna stran za ustvarjanje fraktalov in rastlin iz L-sistemov.
• »Branching: L-system Tree«, mizuno.org (v angleščini) – javanski programček in njegova izvorna koda (odprtokodna) za simulacijo rasti botaničnega drevesa z uporabo L-sistema.
• McWorter, William, »Fractint L-System True Fractals«, spanky.triumf.ca (v angleščini)
• »OpenAlea«, openalea.gforge.inria.fr (v francoščini), arhivirano iz prvotnega spletišča dne 17. oktobra 2005 – odprtokodno programsko okolje za modeliranje rastlin, ki vsebuje L-Py, odprtokodno implementacijo Lindenmayerjevih sistemov v programskem jeziku Python.
• »powerPlant«, sourceforge.net (v angleščini) – odprtokodna programska oprema za modeliranje krajine.
• »An evolutionary L-systems generator (anyos*)«, cs.ucl.ac.uk (v angleščini)
• »rfindler/lindenmayer«, github.com (v angleščini) – implementacija L-sistemov v programskem jeziku Racket.
• Griffiths, Dave (2004), »LsystemComposition«, pawfal.org (v angleščini), arhivirano iz spletišča dne 6. novembra 2004, pridobljeno 19. aprila 2012 – stran o uporabi L-sistemov in genetskih algoritmov za ustvarjanje glasbe.
• »eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP«, grogra.de (v angleščini)
• de Campos, António Miguel, »Fractal figures generated using L-systems«, to-campos.planetaclix.pt (v angleščini), arhivirano iz prvotnega spletišča dne 6. avgusta 2016 – javanski programček z mnogimi fraktalnimi figurami, ki jih generirajo L-sistemi.
• Manousakis, Stelios (junij 2006). Musical L-Systems (PDF) (magistrska naloga) (v angleščini). Kraljevi konservatorij v Haagu. Arhivirano (PDF) iz spletišča dne 23. julija 2011. Pridobljeno 19. julija 2022.
• »L-systems | Online experiments with Lindenmayer Systems«, jsxgraph.uni-bayreuth.de (v angleščini) – L-sistemi, ustvarjeni s programsko opremo JSXGraph (JavaScript)
• »Flea«, flea.sourceforge.net (v angleščini) – implementacija LSYSTEM v programskem jeziku Rubyj, ki uporablja domensko specifični jezik namesto jedrnatih generatorskih ukazov
• »Lindenmayer power«, madflame991.blogspot.com (v angleščini) – generator rastlin in fraktalov z uporabo L-sistemov (JavaScript)
• Rozenberg, Grzegorz; Salomaa, Arto (2001) [1994]. »L-systems«. Encyclopedia of Mathematics. EMS Press.
• »About Lsystems and Lparser ...«, laurenslapre.nl (v angleščini), arhivirano iz prvotnega spletišča dne 13. septembra 2013 – razčlenjevalnik L-Parser Laurensa Lapréja
• »L-System Turtle Graphics Renderer«, kevs3d.co.uk (v angleščini) – HTML5 L-Systems.
• Program za vektorsko grafiko Inkscape ima razčlenjevalnik L-sistema
• Liou, Cheng-Yuan; Wu, Tai-Hei; Lee, Chia-Ying (2009), »Modeling complexity in musical rhythm«, Complexity, 15 (4): 19–30, doi:10.1002/cplx.20291, ISSN 1076-2787, S2CID 18737938
• »Draw fractals using L-system«, xojoc.pw (v angleščini) – implementacija razčlenjevalnika L-sistema in preproste želvje grafike v programskem jeziku Icon
• Carroll, Nolan, »lindenmayer system generator«, nolandc.com (v angleščini)
• »L-Systems with a genetic twist«, bloogen.com (v angleščini)
• Weisstein, Eric Wolfgang. »Lindenmayer System«. MathWorld (v angleščini).

Sklici na zunanje povezave