نظام L
نظام L أو نظام ليندنماير هو نظام إعادة كتابة متوازٍ ونوع من القواعد النحوية الرسمية . يتكون نظام L من أبجدية من الرموز التي يمكن استخدامها لتكوين سلاسل نصية ، ومجموعة من قواعد الإنتاج التي توسع كل رمز إلى سلسلة نصية أكبر، وسلسلة " بديهية " أولية يُبدأ منها البناء، وآلية لترجمة السلاسل المُولَّدة إلى هياكل هندسية. طُوِّرت أنظمة L في عام 1968 على يد أريستيد ليندنماير ، عالم الأحياء النظرية وعالم النبات المجري في جامعة أوتريخت . [ 1 ] استخدم ليندنماير أنظمة L لوصف سلوك الخلايا النباتية ونمذجة عمليات نمو النبات . كما استُخدمت أنظمة L لنمذجة مورفولوجيا مجموعة متنوعة من الكائنات الحية [ 2 ] ويمكن استخدامها لتوليد كسور ذاتية التشابه .
الأصول
عمل ليندنماير، بصفته عالم أحياء، مع الخمائر والفطريات الخيطية ، ودرس أنماط نمو أنواع مختلفة من البكتيريا ، مثل البكتيريا الزرقاء أنابينا كاتينولا . في الأصل، صُممت أنظمة L لتقديم وصف رسمي لتطور هذه الكائنات متعددة الخلايا البسيطة، ولتوضيح العلاقات بين خلايا النبات. لاحقًا، تم توسيع هذا النظام ليشمل وصف النباتات الراقية والهياكل المتفرعة المعقدة.
بنية النظام L
تؤدي الطبيعة التكرارية لقواعد نظام L إلى التشابه الذاتي ، وبالتالي، يسهل وصف الأشكال الشبيهة بالكسور الهندسية باستخدام نظام L. يسهل تعريف نماذج النباتات والأشكال العضوية ذات المظهر الطبيعي، حيث ينمو الشكل تدريجيًا ويصبح أكثر تعقيدًا بزيادة مستوى التكرار. كما تحظى أنظمة ليندنماير بشعبية في توليد الحياة الاصطناعية .
تتشابه قواعد نظام L إلى حد كبير مع قواعد شبه ثيو (انظر التسلسل الهرمي لتشومسكي ). تُعرف أنظمة L الآن باسم أنظمة L البارامترية ، والتي تُعرَّف على أنها مجموعة من العناصر .
- G = ( V , ω, P ),
أين
- V ( الأبجدية ) هي مجموعة من الرموز تحتوي على كل من العناصر التي يمكن استبدالها ( المتغيرات ) وتلك التي لا يمكن استبدالها ("الثوابت" أو "الرموز الطرفية").
- ω ( بداية ، بديهية ، أو مُبادر ) عبارة عن سلسلة من الرموز من V تُحدد الحالة الابتدائية للنظام
- P هي مجموعة من قواعد الإنتاج أو عمليات الإنتاج التي تحدد كيفية استبدال المتغيرات بمجموعات من الثوابت والمتغيرات الأخرى. تتكون عملية الإنتاج من سلسلتين، السابقة واللاحقة . لأي رمز A ينتمي إلى المجموعة V ولا يظهر على الجانب الأيسر من عملية إنتاج في P، يُفترض وجود عملية الإنتاج المحايد A → A؛ وتُسمى هذه الرموز بالثوابت أو الرموز النهائية . (انظر قانون الهوية ).
تُطبَّق قواعد نظام L النحوي بشكل تكراري بدءًا من الحالة الابتدائية. ويُطبَّق أكبر عدد ممكن من القواعد في كل تكرار. إن استخدام أكبر عدد ممكن من القواعد في كل تكرار هو ما يُميِّز نظام L عن اللغة الرسمية المُولَّدة بواسطة قواعد نحوية رسمية ، والتي تُطبِّق قاعدة واحدة فقط في كل تكرار. لو طُبِّقت قواعد الإنتاج واحدة تلو الأخرى، لكان من السهل توليد سلسلة نصية في اللغة، ولأنتج كل تسلسل من هذه التطبيقات اللغة المُحدَّدة بواسطة القواعد النحوية. مع ذلك، توجد بعض السلاسل النصية في بعض اللغات التي لا يُمكن توليدها إذا عُومِلت القواعد النحوية كنظام L بدلاً من كونها مواصفات للغة. على سبيل المثال، [ 3 ] لنفترض وجود قاعدة S→SS في قواعد نحوية. إذا طُبِّقت قواعد الإنتاج واحدة تلو الأخرى، فسنحصل بدءًا من S على SS أولاً، ثم بتطبيق القاعدة مرة أخرى، نحصل على SSS. ولكن، إذا طُبِّقت جميع القواعد المُناسبة في كل خطوة، كما هو الحال في نظام L، فلن نتمكن من الحصول على هذا الشكل الجملي. بدلاً من ذلك، ستعطينا الخطوة الأولى SS، لكن الخطوة الثانية ستطبق القاعدة مرتين، مما يعطينا SSSS. وبالتالي، فإن مجموعة السلاسل التي ينتجها نظام L من قواعد نحوية معينة هي مجموعة جزئية من اللغة الرسمية التي تحددها تلك القواعد، وإذا اعتبرنا أن اللغة تُعرَّف على أنها مجموعة من السلاسل، فهذا يعني أن نظام L معين هو في الواقع مجموعة جزئية من اللغة الرسمية التي تحددها قواعد ذلك النظام.
يُعتبر نظام L خالياً من السياق إذا كانت كل قاعدة إنتاجية تشير فقط إلى رمز فردي دون الإشارة إلى الرموز المجاورة له. وبالتالي، تُحدد أنظمة L الخالية من السياق بواسطة قواعد نحوية خالية من السياق . أما إذا كانت القاعدة تعتمد ليس فقط على رمز واحد، بل أيضاً على الرموز المجاورة له، فتُسمى نظام L حساساً للسياق .
إذا كان هناك إنتاج واحد فقط لكل رمز، يُقال إن نظام L حتمي (يُطلق على نظام L الحتمي الخالي من السياق اسم نظام D0L ). أما إذا كان هناك عدة إنتاجات، ويتم اختيار كل منها باحتمالية معينة خلال كل تكرار، فإنه يُسمى نظام L عشوائي .
يتطلب استخدام أنظمة L لإنشاء الصور الرسومية أن تشير الرموز في النموذج إلى عناصر الرسم على شاشة الحاسوب. على سبيل المثال، يستخدم برنامج Fractint رسومات السلحفاة (المشابهة لتلك الموجودة في لغة برمجة Logo ) لإنتاج صور الشاشة. وهو يفسر كل ثابت في نموذج نظام L كأمر من أوامر السلحفاة.
أمثلة على أنظمة L
مثال 1: الطحالب
نظام ليندنماير الأصلي على شكل حرف L لنمذجة نمو الطحالب.
- المتغيرات : AB
- الثوابت : لا شيء
- البديهية : أ
- القواعد : (أ → أب)، (ب → أ)
والذي ينتج عنه:
- ن = 0 : أ
- ن = 1 : أ ب
- ن = 2 : ABA
- ن = 3 : ABAAB
- ن = 4 : أ ب ...
- ن = 5 : ABAABABAABAAB
- ن = 6 : ABABABAABAABABABABAB
- ن = 7 : أباباباباباباباباباباباباباب
مثال 1: الطحالب، شرح
n=0: بداية (مبدأ/مُبادر) / \ n=1: AB هو العنصر A الأولي الذي تم توليده إلى AB وفقًا للقاعدة (A → AB)، ولا يمكن تطبيق القاعدة (B → A). /| \ n=2: ABA السلسلة السابقة AB مع تطبيق جميع القواعد، A تولد في AB مرة أخرى، B السابقة تحولت إلى A / | | | \ ن=3: ABAAB لاحظ أن جميع A تنتج نسخة من نفسها في المقام الأول، ثم B، والتي تتحول ... / | | | \ | \ \ n=4: ABAABABA ... إلى A بعد جيل واحد، بدء التوليد/التكرار/الاستدعاء الذاتي ثم
والنتيجة هي متتالية كلمات فيبوناتشي . إذا تم حساب طول كل سلسلة، فسيتم الحصول على متتالية أرقام فيبوناتشي (مع تخطي الرقم 1 الأول، بسبب اختيار البديهية):
- 1 2 3 5 8 13 21 34 55 89 ...
إذا لم يكن من المرغوب فيه تخطي الرقم 1 الأول، فيمكن استخدام البديهية B. سيؤدي ذلك إلى وضع عقدة B قبل العقدة العلوية ( A ) في الرسم البياني أعلاه.
بالنسبة لكل سلسلة، إذا تم حساب الموضع k من الطرف الأيسر للسلسلة، فإن القيمة تُحدد بناءً على ما إذا كان مضاعف النسبة الذهبية يقع ضمن الفترةوبالمثل، فإن نسبة A إلى B تتقارب إلى النسبة الذهبية.
هذا المثال يعطي نفس النتيجة (من حيث طول كل سلسلة، وليس تسلسل A و B ) إذا تم استبدال القاعدة ( A → AB ) بـ ( A → BA )، باستثناء أن السلاسل معكوسة.
هذا التسلسل هو تسلسل متسلسل محليًا لأن، أينهو الجيل رقم ن .
مثال 2: شجرة كسورية (ثنائية)
- المتغيرات : 0، 1
- الثوابت : "[", "]"
- البديهية : 0
- القواعد : (1 → 11)، (0 → 1[0]0)
يتم بناء الشكل من خلال تمرير البديهية بشكل متكرر عبر قواعد الإنتاج. يتم فحص كل حرف من سلسلة الإدخال مقابل قائمة القواعد لتحديد الحرف أو السلسلة التي سيتم استبداله بها في سلسلة الإخراج. في هذا المثال، يصبح الرقم '1' في سلسلة الإدخال '11' في سلسلة الإخراج، بينما يبقى الرمز ' [ ' كما هو. بتطبيق هذا على بديهية الرقم '0'، نحصل على:
| البديهية: | 0 |
| الاستدعاء الذاتي الأول: | 1 [0] 0 |
| الاستدعاء الثاني: | 11[1[0]0]1[0]0 |
| الاستدعاء الثالث: | 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0 |
| ... |
يتضح أن هذا النص يزداد حجمًا وتعقيدًا بسرعة. يمكن تمثيل هذا النص كصورة باستخدام رسومات السلحفاة ، حيث يُخصص لكل رمز عملية رسومية تقوم السلحفاة بتنفيذها. على سبيل المثال، في المثال أعلاه، يمكن إعطاء السلحفاة التعليمات التالية:
- 0: ارسم قطعة مستقيمة تنتهي بورقة
- 1: ارسم قطعة مستقيمة
- [ : ادفع الوضع والزاوية، ثم أدر إلى اليسار 45 درجة
- ] : اضبط موضع وزاوية الفتح، ثم استدر يمينًا بزاوية 45 درجة
يشير كل من push و pop إلى مكدس LIFO (في قواعد اللغة الأكثر تخصصًا، توجد رموز منفصلة لـ "دفع الموضع" و "الانعطاف يسارًا"). عندما يصادف تفسير السلحفاة الرمز ' [ '، يتم حفظ الموضع والزاوية الحاليين، ثم يتم استعادتهما عند مصادفة الرمز ' ] '. إذا تم "دفع" قيم متعددة، فإن "pop" يستعيد القيم المحفوظة مؤخرًا. بتطبيق القواعد الرسومية المذكورة أعلاه على الاستدعاء الذاتي السابق، نحصل على:
بديهية
الاستدعاء الذاتي الأول
التكرار الثاني
التكرار الثالث
التكرار الرابع
التكرار السابع، مصغر عشر مرات
مثال 3: مجموعة كانتور
- المتغيرات : AB
- الثوابت : لا شيء
- البداية : سلسلة الأحرف البادئة {A }
- القواعد : (أ → أ ب أ)، (ب → ب ب ب)
لنفترض أن A تعني "التقدم للأمام" و B تعني "التحرك للأمام".
ينتج عن هذا مجموعة كانتور الكسورية الشهيرة على خط مستقيم حقيقي R.
المثال 4: منحنى كوخ
نوع من منحنى كوخ يستخدم الزوايا القائمة فقط.
- المتغيرات : F
- الثوابت : + −
- البداية : F
- القواعد : (F → F+F − F − F+F)
هنا، F تعني "التحرك للأمام"، و+ تعني "الانعطاف لليسار 90 درجة"، و- تعني "الانعطاف لليمين 90 درجة" (انظر رسومات السلحفاة ).
- ن = 0:
- F
- ن = 1:
- F+F − F − F+F
- ن = 2:
- F+F − F − F+F+F+ F − F − F + F − F + F − F − F+F − F − F+F+F+F − F − F+F
- ن = 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
مثال 5: مثلث سيربينسكي
مثلث سيربينسكي المرسوم باستخدام نظام L.
- المتغيرات : FG
- الثوابت : + −
- البداية : F − G − G
- القواعد : (F → F − G+F+G − F)، (G → GG)
- الزاوية : 120 درجة
هنا، F و G كلاهما يعني "التقدم للأمام"، و + يعني "الانعطاف لليسار بزاوية"، و − يعني "الانعطاف لليمين بزاوية".
ن = 2
ن = 4
ن = 6
من الممكن أيضًا تقريب مثلث سيربينسكي باستخدام نظام منحنى رأس السهم سيربينسكي L.
- المتغيرات : AB
- الثوابت : + −
- البداية : أ
- القواعد : (أ → ب − أ − ب)، (ب → أ+ب+أ)
- الزاوية : 60 درجة
هنا، A و B كلاهما يعني "السحب للأمام"، و + يعني "الانعطاف لليسار بزاوية"، و − يعني "الانعطاف لليمين بزاوية" (انظر رسومات السلحفاة ).
المثال 6: منحنى التنين
منحنى التنين المرسوم باستخدام نظام L.
- المتغيرات : FG
- الثوابت : + −
- البداية : F
- القواعد : (F → F+G)، (G → FG)
- الزاوية : 90 درجة
هنا، F و G كلاهما يعني "التقدم للأمام"، و + يعني "الانعطاف لليسار بزاوية"، و − يعني "الانعطاف لليمين بزاوية".
مثال 7: نبات فركتالي
- المتغيرات : XF
- الثوابت : + − [ ]
- بدء التشغيل : -X
- القواعد : (X → F+[[X]-X]-F[-FX]+X)، (F → FF)
- الزاوية : 25 درجة
أولًا، يجب تهيئة مكدس فارغ. يتم ذلك باتباع طريقة LIFO (آخر ما يدخل، أول ما يخرج) لإضافة العناصر وإزالتها. هنا، F تعني "الرسم للأمام"، و- تعني "الانعطاف يمينًا 25 درجة"، و+ تعني "الانعطاف يسارًا 25 درجة". لا يرتبط X بأي عملية رسم، وإنما يُستخدم للتحكم في تطور المنحنى. يشير القوس المربع "[" إلى حفظ القيم الحالية للموضع والزاوية، لذا يتم دفع الموضع والزاوية إلى أعلى المكدس. عند مصادفة الرمز "]"، يتم إخراج عنصر من المكدس وإعادة ضبط الموضع والزاوية. كل "[" يسبق كل "]".
الاختلافات
تم تطوير عدد من التوسعات على تقنية نظام L الأساسية هذه، والتي يمكن استخدامها بالتزامن مع بعضها البعض. ومن بين هذه التوسعات القواعد النحوية العشوائية ، والقواعد النحوية الحساسة للسياق ، والقواعد النحوية البارامترية.
القواعد النحوية العشوائية
كان نموذج القواعد الذي ناقشناه حتى الآن حتميًا، أي أنه لأي رمز في أبجدية القواعد، توجد قاعدة إنتاج واحدة فقط، يتم اختيارها دائمًا، وتؤدي دائمًا إلى نفس التحويل. أحد البدائل هو تحديد أكثر من قاعدة إنتاج للرمز، مع إعطاء كل منها احتمالًا للظهور . على سبيل المثال، في قواعد المثال 2، يمكننا تغيير قاعدة إعادة كتابة "0" من:
- 0 → 1[0]0
إلى قاعدة احتمالية:
- 0 (0.5) → 1[0]0
- 0 (0.5) → 0
في ظل هذا الإنتاج، عند مصادفة الرقم "0" أثناء إعادة كتابة السلسلة، يكون هناك احتمال بنسبة 50% أن يتصرف كما وُصف سابقًا، واحتمال بنسبة 50% ألا يتغير أثناء الإنتاج. عند استخدام قواعد نحوية عشوائية في سياق تطوري ، يُنصح بتضمين بذرة عشوائية في النمط الجيني ، بحيث تظل الخصائص العشوائية للصورة ثابتة بين الأجيال.
قواعد نحوية حساسة للسياق
لا تنظر قاعدة الإنتاج الحساسة للسياق إلى الرمز الذي تُعدّله فحسب، بل تنظر أيضًا إلى الرموز الموجودة في السلسلة النصية التي تظهر قبله وبعده. على سبيل المثال، قاعدة الإنتاج:
- ب < أ > ج → أأ
يحول "a" إلى "aa"، ولكن فقط إذا ظهر الحرف "a" بين الحرفين "b" و "c" في سلسلة الإدخال:
- …العودة…
كما هو الحال مع قواعد الإنتاج الاحتمالية، توجد قواعد إنتاج متعددة للتعامل مع الرموز في سياقات مختلفة. إذا لم يُعثر على قاعدة إنتاج لسياق معين، يُفترض استخدام قاعدة الإنتاج المحايد، ولا يتغير الرمز عند التحويل. إذا وُجدت قواعد إنتاج حساسة للسياق وأخرى غير حساسة له ضمن نفس القواعد النحوية، يُفترض أن تكون لقاعدة الإنتاج الحساسة للسياق الأولوية عند انطباقها.
القواعد النحوية البارامترية
في القواعد النحوية البارامترية، يرتبط كل رمز في الأبجدية بقائمة من المعاملات. يُطلق على الرمز المرتبط بقائمة معاملاته اسم "وحدة نمطية"، والسلسلة النصية في القواعد النحوية البارامترية هي عبارة عن سلسلة من الوحدات النمطية. مثال على سلسلة نصية:
- a(0,1)[b(0,0)]a(1,2)
يمكن استخدام هذه المعلمات بواسطة وظائف الرسم، وكذلك بواسطة قواعد الإنتاج. ويمكن لقواعد الإنتاج استخدام هذه المعلمات بطريقتين: أولاً، في عبارة شرطية لتحديد ما إذا كانت القاعدة ستنطبق، وثانياً، يمكن لقاعدة الإنتاج تعديل المعلمات الفعلية. على سبيل المثال، انظر إلى:
- أ(س،ص) : س == 0 → أ(1، ص+1)ب(2,3)
يخضع الموديول a(x,y) للتحويل وفقًا لقاعدة الإنتاج هذه إذا تحقق الشرط x=0. على سبيل المثال، سيخضع الموديول a(0,2) للتحويل، بينما لن يخضع الموديول a(1,2) له.
في جزء التحويل من قاعدة الإنتاج، يمكن أن تتأثر المعاملات وكذلك الوحدات النمطية بأكملها. في المثال أعلاه، تُضاف الوحدة النمطية b(x,y) إلى السلسلة، بمعاملات أولية (2،3). كما يتم تحويل معاملات الوحدة النمطية الموجودة مسبقًا. وفقًا لقاعدة الإنتاج المذكورة أعلاه،
- أ(0،2)
يصبح
- أ(1،3)ب(2،3)
حيث يتم تحويل المعامل "x" لـ a(x,y) بشكل صريح إلى "1" ويتم زيادة المعامل "y" لـ a بمقدار واحد.
تسمح القواعد النحوية البارامترية بتحديد أطوال الخطوط وزوايا التفرع بواسطة القواعد النحوية نفسها، بدلاً من طرق تفسير السلحفاة. كذلك، إذا تم تحديد العمر كمعامل لوحدة نمطية، يمكن تغيير القواعد تبعًا لعمر جزء من النبات، مما يسمح بإنشاء رسوم متحركة لدورة حياة الشجرة بأكملها.
القواعد النحوية ثنائية الاتجاه
يفصل النموذج ثنائي الاتجاه نظام إعادة الكتابة الرمزية صراحةً عن عملية تحديد الشكل. فعلى سبيل المثال، عملية إعادة كتابة السلسلة في المثال 2 (الشجرة الكسورية) مستقلة عن كيفية تعيين العمليات الرسومية للرموز. بعبارة أخرى، يمكن تطبيق عدد لا نهائي من طرق الرسم على نظام إعادة كتابة معين.
يتألف النموذج ثنائي الاتجاه من: 1) عملية أمامية تُنشئ شجرة الاشتقاق باستخدام قواعد الإنتاج، و2) عملية عكسية تُجسّد الشجرة باستخدام الأشكال بشكل تدريجي (من الأوراق إلى الجذر). تتضمن كل خطوة من خطوات الاشتقاق العكسي استدلالًا هندسيًا-طوبولوجيًا أساسيًا. باستخدام هذا الإطار ثنائي الاتجاه، تُشفّر قيود التصميم وأهدافه في ترجمة القواعد النحوية إلى أشكال. في تطبيقات التصميم المعماري، تتميز القواعد النحوية ثنائية الاتجاه بترابط داخلي متسق وتسلسل هرمي مكاني غني. [ 4 ]
بناء نظام L والاستدلال
بناء نظام L يدوي
تاريخيًا، اعتمد بناء أنظمة L بشكل كبير على الجهود اليدوية للخبراء، [ 5 ] [ 6 ] [ 7 ] مما تطلب قياسات دقيقة ومعرفة متخصصة واستثمارًا كبيرًا للوقت. غالبًا ما تضمنت العملية تحليل البنى البيولوجية وتشفير قواعد نموها في أنظمة L، رمزًا رمزًا. هذه الطريقة كثيفة العمالة جعلت إنشاء نماذج دقيقة للعمليات المعقدة أمرًا شاقًا وعرضة للأخطاء.
من الأمثلة البارزة على ذلك عمل نيشيدا [ 7 ] على أشجار السرو الياباني، حيث قام بتقسيم الأغصان يدويًا من سلسلة من الصور، وحدد 42 آلية نمو متميزة لبناء نظام L عشوائي. على الرغم من الجهد الكبير المبذول، لم يقدم النظام الناتج سوى تقريب لنمو الشجرة، مما يوضح صعوبة ترميز مثل هذه العمليات البيولوجية التفصيلية يدويًا. وُصفت هذه المهمة الشاقة بأنها "مملة ومعقدة"، مما يؤكد محدودية الأساليب اليدوية.
تُوثَّق تحديات بناء أنظمة L يدويًا بشكلٍ وافٍ في كتاب "الجمال الخوارزمي للنباتات" [ 6 ] للمؤلفين برزيميسلاف بروسينكيويتش وأريستيد ليندنماير. يُبيّن الكتاب كيف يُمكن لأنظمة L أن تُحاكي نمو النباتات والأنماط الكسورية بدقةٍ عالية، إلا أن الأمثلة غالبًا ما تتطلب تدخلًا من الخبراء لتحديد القواعد اللازمة.
وقد زاد من قيود البناء اليدوي الحاجة إلى خبرة متخصصة في المجال، كما هو الحال في تطبيقات أخرى لأنظمة L خارج نطاق علم الأحياء، مثل التصميم المعماري والنمذجة الحضرية. [ 8 ] في هذه المجالات، لم يتطلب إنشاء نظام L دقيق فهمًا لشكلية نظام L فحسب، بل تطلب أيضًا معرفة واسعة بالمجال الذي يتم نمذجته.
الاستدلال بنظام L
ظهرت فكرة أتمتة استدلال أنظمة L لمعالجة أوجه القصور في الطرق اليدوية، التي غالباً ما تتطلب خبرة واسعة، وقياسات، وعمليات تجريبية. وتهدف هذه الأتمتة إلى تمكين استدلال أنظمة L مباشرةً من البيانات الرصدية، مما يلغي الحاجة إلى الترميز اليدوي للقواعد.
استهدفت الخوارزميات الأولية في المقام الأول أنظمة L الحتمية الخالية من السياق (أنظمة D0L)، والتي تُعد من أبسط أنواع أنظمة L. وقد أظهرت هذه الجهود المبكرة جدوى الاستدلال التلقائي، لكنها كانت محدودة النطاق للغاية، حيث اقتصرت عادةً على التعامل مع الأنظمة ذات الأبجديات الصغيرة وقواعد إعادة الكتابة البسيطة. [ 9 ] [ 10 ] [ 11 ] [ 12 ] على سبيل المثال، أبرز عمل ناكانو [ 10 ] تحديات استدلال أنظمة L ذات الأبجديات الأكبر حجمًا والهياكل الأكثر تعقيدًا، واصفًا المهمة بأنها "معقدة للغاية".
الأدوات اليدوية وشبه الآلية
صُممت الأدوات المبكرة لاستنتاج أنظمة L غالبًا لمساعدة الخبراء لا لاستبدالهم. فعلى سبيل المثال، ساهمت الأنظمة التي عرضت على المستخدم مجموعة من أنظمة L المحتملة، مما أتاح له اختيار الخيارات المناسبة من الناحية الجمالية أو المعقولة، في تخفيف بعض العبء اليدوي. [ 12 ] [ 13 ] ومع ذلك، اعتمدت هذه الأدوات بشكل كبير على التقييم البشري ولم تؤتمت عملية الاستنتاج بشكل كامل.
أساليب الاستدلال الخاصة بالمجال
تم دمج بعض الخوارزميات المبكرة بشكل وثيق في مجالات بحثية محددة، ولا سيما نمذجة النباتات. [ 13 ] وقد استغلت هذه المناهج المعرفة المتخصصة بالمجال لتقييد نطاق البحث وتحقيق نتائج أفضل. ومع ذلك، فإن اعتمادها على قواعد محددة مسبقًا خاصة بالمجال حدّ من قابليتها للتعميم والتطبيق في مجالات أخرى.
خوارزميات الاستدلال المعممة
بدأت محاولات ابتكار خوارزميات معممة لاستنتاج أنظمة L بأنظمة حتمية خالية من السياق. سعى الباحثون إلى استنتاج أنظمة L من البيانات وحدها، مثل سلاسل النصوص أو البيانات الزمنية من الصور، دون الاعتماد على معرفة خاصة بالمجال. واجهت هذه الخوارزميات تحديات كبيرة، [ 14 ] [ 15 ] منها:
- النمو الأسي لمساحة البحث مع زيادة حجم الأبجدية وتعقيد القواعد.
- التعامل مع البيانات غير الكاملة أو المشوشة، مما أدى إلى حدوث أخطاء في الأنظمة المستنتجة.
- القيود في الكفاءة الحسابية، حيث أصبحت طرق البحث الشاملة غير قابلة للتطبيق في جميع الحالات باستثناء أبسطها.
تمثل أطروحة الدكتوراه التي قدمها برنارد، [ 16 ] بإشراف الدكتور إيان ماكويلان في جامعة ساسكاتشوان، تقدماً هاماً في مجال استنتاج أنظمة L، حيث قدمت مجموعة أدوات استنتاج نموذج النبات (PMIT). وعلى الرغم من اسمها، فإن هذه الأداة لا تقتصر على مشكلة محددة، وقد سُميت بهذا الاسم نسبةً إلى مصدر التمويل الأصلي من مشروع P2IRC. وتعالج هذه الأدوات تحديات استنتاج أنظمة L الحتمية والعشوائية والبارامترية.
أنظمة L الحتمية الخالية من السياق (D0L):
حسّنت أداة PMIT-D0L من أحدث التقنيات من خلال تمكين استنتاج أنظمة L التي تحتوي على ما يصل إلى 31 رمزًا، مقارنةً بالخوارزميات السابقة التي كانت تتعامل مع رمزين فقط. وقد تحقق ذلك من خلال تقنيات ترميز مبتكرة وأساليب لتقليل مساحة البحث.
أنظمة L الحتمية الحساسة للسياق (D(j,k)L):
حسّنت أداة PMIT-DCSL بشكلٍ ملحوظ عملية استنتاج أنظمة L الحتمية، مُثبتةً فعالية التقنيات في حالة الأنظمة الحساسة للسياق مع تعديلات طفيفة. كما قدمت هذه الأداة تحسينات إضافية سمحت باستنتاج أنظمة L الحتمية التي تصل إلى مئات الرموز. علاوة على ذلك، يُثبت هذا العمل والورقة النظرية لماكويلان [ 17 ] تعقيد استنتاج أنظمة L الحساسة للسياق. في عمل غير منشور، يدّعي برنارد أنه يُظهر أن حساسية السياق لا تُغير أبدًا الطبيعة الأساسية لمشكلة الاستنتاج بغض النظر عن قاعدة الاختيار. أي أن استنتاج أنظمة L العشوائية الحساسة للسياق ممكن إذا كان استنتاج أنظمة L غير الحساسة للسياق ممكنًا.
أنظمة L العشوائية (S0L):
بالنسبة لأنظمة L العشوائية، تم تطوير PMIT-S0L، الذي يستخدم نهجًا هجينًا يجمع بين الخوارزمية الجشعة والخوارزمية الجينية لاستنتاج الأنظمة من سلاسل نصية متعددة. وقد أظهرت الأداة قدرةً على استنتاج قواعد إعادة الكتابة والاحتمالات بدقة عالية، وهو إنجاز غير مسبوق في هذا المجال.
أنظمة L البارامترية الزمنية:
أدرك ماكويلان في البداية أن أنظمة L البارامترية يُمكن اعتبارها أنظمة L عشوائية؛ إلا أن هذا لم يحل مشكلة استنتاج قواعد الاختيار البارامترية. باستخدام البرمجة الجينية الديكارتية، أمكن استنتاج أنظمة L البارامترية مع قواعد الاختيار البارامترية طالما تضمنت مجموعة المعلمات الزمن (لتوفير تسلسل للمعلمات، مع العلم أن الزمن معلمة مناسبة لأي عملية حقيقية). نجحت هذه الأداة، PMIT-PARAM، في استنتاج أنظمة معقدة تصل إلى 27 قاعدة إعادة كتابة، مما وضع معيارًا جديدًا في استنتاج أنظمة L.
المشكلات المفتوحة
توجد العديد من المشكلات المفتوحة المتعلقة بدراسات أنظمة L. على سبيل المثال:
- توصيف جميع أنظمة L الحتمية الخالية من السياق والتي تتميز بالتسلسل المحلي . (لا يُعرف حل كامل إلا في حالة وجود متغيرين فقط). [ 18 ]
أنواع أنظمة L
أنظمة L على الخط الحقيقي R :
من أشهر أنظمة L على مستوى R 2 ما يلي:
- المنحنيات التي تملأ الفراغ ( منحنى هيلبرت ، منحنيات بيانو ، كنيسة ديكينغ، الكولام )،
- منحنيات ملء الفراغ المتوسطة ( منحنى ليفي سي ، منحنى هارتر-هايواي التنيني ، منحنى ديفيس-كنوث التنيني)،
- التبليط ( تبليط أبو الهول ، تبليط بنروز )
انظر أيضاً
- التشكّل الرقمي
- نظام الدوال المتكررة
- نظام التفاعل والانتشار - نوع من النماذج الرياضية التي توفر محاكاة انتشار الكواشف الكيميائية (بما في ذلك المحاكاة الشبيهة بالحياة)
- قواعد نحوية عشوائية خالية من السياق
- الجمال الخوارزمي للنباتات
ملحوظات
- ↑ ليندنماير، أريستيد (مارس 1968). "النماذج الرياضية للتفاعلات الخلوية في النمو II. الخيوط البسيطة والمتفرعة ذات المدخلات ثنائية الجانب". مجلة البيولوجيا النظرية . 18 (3): 300-315 . Bibcode : 1968JThBi..18..300L . doi : 10.1016/0022-5193(68)90080-5 . ISSN 0022-5193 . PMID 5659072 .
- ↑ غريغورز روزنبرغ وأرتو سالوما. النظرية الرياضية لأنظمة L (دار النشر الأكاديمية، نيويورك، 1980). ISBN 0-12-597140-0
- ↑ "أنظمة L" . موسوعة الرياضيات . سبرينغر . تم الاطلاع عليه بتاريخ 26 يوليو 2022 .
- ↑ هوا، هـ.، ديسمبر 2017. نموذج إجرائي ثنائي الاتجاه للتصميم المعماري . في منتدى رسومات الحاسوب (المجلد 36، العدد 8، الصفحات 219-231).
- ↑ دينوس فريجترز وأريستيد ليندنماير. نموذج لنمو وازدهار نبات أستر نوفا أنجليا بناءً على الجدول < 10 > أنظمة L. في أنظمة L، الصفحات 2452. سبرينغر، 1974.
- 1 2 بروسينكيويتش، ب.، وليندنماير، أ. (2012). الجمال الخوارزمي للنباتات . سبرينغر ساينس آند بيزنس ميديا.
- 1 2 T. Nishida, K0L-system simulating almost but not exact the same development-case of Japanese Cypress, Memoirs of the Faculty of Science, Kyoto University, Series B 8 (1) (1980) 97122.
- ↑ باسكال مولر، بيتر وونكا، سيمون هيغلر، أندرياس أولمر، ولوك فان غول. النمذجة الإجرائية للمباني. معاملات ACM في الرسومات، 25(3):614-623، 2006.
- ↑ بيان رونكيانغ، فيبي تشين، كيفن بوراج، جيم هانان، بيتر روم، وجون بيلوارد. اشتقاق نماذج نظام L من قياسات هياكل التفرع البيولوجية باستخدام الخوارزميات الجينية. في وقائع المؤتمر الدولي حول التطبيقات الصناعية والهندسية وغيرها من تطبيقات الأنظمة الذكية التطبيقية، الصفحات 514-524. سبرينغر، 2002.
- 1 2 ريوهي ناكانو. الاستقراء الناشئ لقواعد نظام L الحتمية الخالية من السياق. في الابتكارات في الحوسبة والتطبيقات المستوحاة من علم الأحياء، الصفحات 75-84. دار نشر سبرينغر الدولية، 2014.
- ↑ بي جي دوسيه. مشكلة الاستدلال النحوي لتسلسلات D0L. أنظمة L، الصفحات 146-161، 1974
- 1 2 روجر كاري. حول تطور أنظمة L البارامترية. تقرير فني، جامعة كالجاري، 2000.
- 1 2 فابريسيو أناستاسيو، برزيميسلاف بروسينكيويتش، وماريو كوستا سوزا. تحديد معلمات أنظمة L باستخدام خطوط بناء مستوحاة من الرسوم التوضيحية وتعديل العمق. الحوسبة والرسومات، 33(4):440-451، 2009.
- ↑ كولين دي لا هيغيرا. دراسة ببليوغرافية للاستدلال النحوي. التعرف على الأنماط، 38(9):1332 1348، 2005.
- ^ كاري، إل.، روزنبرغ، جي.، وسالوما، أ. (1997). أنظمة L (ص 253-328). سبرينغر برلين هايدلبرغ.
- ↑ برنارد، ج. (2020). استنتاج أنواع مختلفة من أنظمة ليندنماير باستخدام الذكاء الاصطناعي (أطروحة دكتوراه، جامعة ساسكاتشوان).
- ↑ ماكويلان، آي.، برنارد، ج.، وبروسينكيويتش، ب. (2018). خوارزميات لاستنتاج أنظمة L الحساسة للسياق. في الحوسبة غير التقليدية والحوسبة الطبيعية: المؤتمر الدولي السابع عشر، UCNC 2018، فونتينبلو، فرنسا، 25-29 يونيو 2018، وقائع المؤتمر 17 (ص 117-130). دار نشر سبرينغر الدولية.
- ↑ كاري، ليلا؛ روزنبرغ، غريغورز؛ سالوما، أرتو (1997). "أنظمة L". دليل اللغات الرسمية . ص 253-328 . doi : 10.1007/978-3-642-59136-5_5 . ISBN 978-3-642-63863-3.
الكتب
- برزيميسواف بروسينكيويتش ، أريستيد ليندنماير - الجمال الخوارزمي للنباتات. نسخة PDF متاحة هنا مجانًا. مؤرشفة بتاريخ 10 أبريل 2021 على موقع Wayback Machine.
- غريغورز روزنبرغ ، أرتو سالوما – أنظمة ليندنماير: تأثيراتها على علوم الحاسوب النظرية، ورسومات الحاسوب، وعلم الأحياء النمائي ISBN 978-3-540-55320-5
- دي إس إيبرت، إف كيه موسغريف، وآخرون - التكسية والنمذجة: منهج إجرائي ، رقم ISBN 0-12-228730-4
- بوري، جين، بوري مارك، (2010). الرياضيات الجديدة للهندسة المعمارية، نيويورك: تيمز وهدسون.
- أريستيد ليندنماير، " النماذج الرياضية للتفاعل الخلوي في النمو ". مجلة علم الأحياء النظري، 18:280-315، 1968.
روابط خارجية
- علم النبات الخوارزمي في جامعة كالجاري
- أنظمة L : صفحة سهلة الاستخدام لإنشاء الأشكال الكسورية والنباتات من أنظمة L.
- التفرع: شجرة نظام L تطبيق جافا صغير وشفرته المصدرية ( مفتوحة المصدر ) لمحاكاة نمو الأشجار النباتية باستخدام نظام L.
- نظام Fractint L للكسور الحقيقية
- OpenAlea مؤرشفة في 2005-10-17 في Wayback Machine : بيئة برمجية مفتوحة المصدر لنمذجة النباتات، [ 1 ] والتي تحتوي على L-Py ، وهو تطبيق بايثون مفتوح المصدر لأنظمة Lindenmayer [ 2 ]
- "powerPlant" هو برنامج مفتوح المصدر لنمذجة المناظر الطبيعية
- مولد أنظمة L التطورية (anyos*)
- تطبيق أنظمة L في لغة Racket
- غريفيث، ديف (2004). "LsystemComposition" . باوفال . مؤرشف من الأصل بتاريخ 6 نوفمبر 2004. تم الاطلاع عليه بتاريخ 19 أبريل 2012 .صفحة تتناول استخدام أنظمة L والخوارزميات الجينية لتوليد الموسيقى.
- أنظمة L الموسعة (XL)، وقواعد النمو العلائقي، ومنصة البرمجيات مفتوحة المصدر GroIMP.
- تطبيق جافا صغير يحتوي على العديد من الأشكال الكسورية المولدة بواسطة أنظمة L. مؤرشف بتاريخ 6 أغسطس 2016 في أرشيف الإنترنت (Wayback Machine).
- مانوساكيس، ستيليوس (يونيو 2006). أنظمة L الموسيقية (ملف PDF) (رسالة ماجستير). المعهد الملكي للموسيقى في لاهاي . مؤرشف (ملف PDF) من الأصل بتاريخ 23 يوليو 2011. تاريخ الاطلاع: 19 يوليو 2022 .
- تجارب عبر الإنترنت باستخدام أنظمة L باستخدام JSXGraph (جافا سكريبت)
- Flea هو تطبيق Ruby لـ LSYSTEM، يستخدم لغة خاصة بالمجال بدلاً من أوامر المولد المختصرة
- طاقة ليندنماير: محطة توليد طاقة ووحدة توليد كسورية باستخدام أنظمة L (جافا سكريبت)
- روزنبرغ، ج.؛ سالوما، أ. (2001) [1994]، "أنظمة L" ، موسوعة الرياضيات ، دار نشر EMS
- تمت أرشفة محلل اللغة L الخاص بلورنس لابري في 13 سبتمبر 2013 على موقع Wayback Machine.
- أنظمة HTML5 L – جرّب التجارب عبر الإنترنت
- يحتوي برنامج الرسومات المتجهة Inkscape على محلل نظام L
- ليو، تشنغ يوان؛ وو، تاي هي؛ لي، تشيا يينغ (2009). "نمذجة التعقيد في الإيقاع الموسيقي". التعقيد . 15 (4): 19-30 . doi : 10.1002/cplx.20291 . S2CID 18737938 .
- تطبيق لمحلل نظام L ورسومات سلحفاة بسيطة بلغة برمجة Icon
- مولد نظام ليندنمير من تأليف نولان كارول
- بلوجن: أنظمة L ذات طابع جيني
- استنتاج أنواع مختلفة من أنظمة ليندنماير باستخدام الذكاء الاصطناعي
- ↑ برادال، كريستوف؛ فورنييه، كريستيان؛ فالدوريز، باتريك؛ كوهين-بولاكيا، سارة (2015). "OpenAlea". وقائع المؤتمر الدولي السابع والعشرين لإدارة قواعد البيانات العلمية والإحصائية (ملف PDF) . الصفحات 1-6 . doi : 10.1145/2791347.2791365 . ISBN 9781450337090. S2CID 14246115 . مؤرشف (PDF) من الأصل بتاريخ 2019-10-17.
- ↑ بودون، فريدريك؛ برادال، كريستوف؛ كوكيلير، توماس؛ بروسينكيويتش، برزيميسلاف؛ غودان، كريستوف (2012). " L-Py: إطار محاكاة نظام L لنمذجة تطور بنية النبات استنادًا إلى لغة ديناميكية" . مجلة Frontiers in Plant Science . 3 : 76. Bibcode : 2012FrPS....3...76B . doi : 10.3389/fpls.2012.00076 . PMC 3362793. PMID 22670147 .
- أنظمة L