Reduction System

A system in which words (expressions) of a formal language can be transformed according to a finite set of rewrite rules is called a reduction system. While reduction systems are also known as string rewriting systems or term rewriting systems, the term "reduction system" is more general.

Lambda calculus is an example of a reduction system with lambda conversion rules constituting its rewrite rules.

If none of the rewrite rules of a reduction system apply to expression , then  is said to be in normal form for a reduction system.

A pair of expressions  is called joinable if both  and  can be reduced to the same expression in zero or more reduction steps (i.e., applications of rewrite rules).

If  is reduced to  in one step, this is indicated . If  is reduced to  in zero or more steps, this is indicated . The notation  is used if there is a sequence {a_0,...,a_n}" src="https://mathworld.wolfram.com/images/equations/ReductionSystem/Inline13.svg" style="height:24px; width:88px" /> such that , , and for every pair , either  or .multinomial coefficient calculator

---

REFERENCES

Baader, F. and Nipkow, T. Term Rewriting and All That. Cambridge, England: Cambridge University Press, 1999.

اخر الاخبار

اخبار العتبة العباسية المقدسة

رئيس قسم الإعلام يبحث مع رئيس جامعة العميد آفاق التعاون في مجال تغطية الأنشطة العلمية والأكاديمية

قسم بين الحرمين يباشر أعمال صيانة الأرصفة في الساحة الوسطية والمناطق المحيطة بها وإدامتها

قسم الشؤون الفكرية ينظم حفل التكليف الشرعي للفتيات في بغداد تيمنًا بذكرى المولد النبوي الشريف

انطلاق النسخة التاسعة من البرنامج التطويري لمشروع (حاملة الرسالة الزينبية)

المزيد

الآخبار الصحية

هل يتنبأ الذكاء الاصطناعي بأمراضنا قبل حدوثها؟

وداعا للنظارات.. قطرة عين واحدة قد تغير كل شيء ؟

دراسة تكشف تأثير "تيك توك" وتطبيقات الفيديو على سلوك الأطفال

"أسرار خفية" في الشاي الأخضر.. تغير قواعد الصحة والوزن

المزيد

الآخبار التكنلوجية

أول قطار يعمل بالهيدروجين في أميركا يدخل الخدمة رسميًا

أجهزة أبل القادمة.. "حصن منيع" في عصر الهجمات الرقمية !

روسيا: تطلق قمرين اصطناعيين بواسطة الصاروخ سويوز 2.1

ميزة ثورية.. أبل تدخل عالم قياس ضغط الدم

المزيد

مواضيع ذات صلة

Lemma

Proof

Zeno,s Paradoxes

Unexpected Hanging Paradox

Strange Loop

Sorites Paradox

Simpson,s Paradox

Russell,s Antinomy

Paradox

Newcomb,s Paradox

Missing Dollar Paradox

Line Point Picking