Confluent

 

A reduction system is called confluent (or globally confluent) if, for all , , and  such that  and , there exists a  such that  and . A reduction system is said to be locally confluent if, for all , ,  such that  and , there exists a  such that  and . Here, the notation  indicates that  is reduced to  in one step, and  indicates that  is reduced to  in zero or more steps.

A reduction system is confluent iff it has Church-Rosser property (Wolfram 2002, p. 1036). In finitely terminating reduction systems, global and local confluence are equivalent, for instance in the systems shown above. Reduction systems that are both finitely terminating and confluent are called convergent. In a convergent reduction system, unique normal forms exist for all expressions.

The problem of determining whether a given reduction system is confluent is recursively undecidable.

The property of being confluent is called confluence. Confluence is a necessary condition for causal invariance.

---

REFERENCES

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

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 507 and 1036-1037, 2002.

اخر الاخبار

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

المجمع العلمي يقيم برنامجًا قرآنيًّا رمضانيًّا في جامعة الكوفة

الحلقة 21 من جائزة العميد القرآنية تشهد تأهل القارئ محمد حسن زاده من أفغانستان إلى المرحلة النهائية

موكب أهالي كربلاء يحيي ذكرى شهادة الإمام علي (عليه السلام) عند مرقده الطاهر

لليوم الثالث.. شعبة الخطابة تنظم مجالس العزاء لإحياء ذكرى شهادة الإمام علي (عليه السلام)

المزيد

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

تأثير اللياقة البدنية على الدماغ

تجربة سريرية تظهر فوائد اللوز للمصابين بالسمنة

اكتشاف طريقة غير متوقعة لتقليل خطر الإصابة بالسكري

خمسة مؤشرات صحية مهملة قد تنقذ حياتك

المزيد

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

علماء الجيولوجيا يفكون لغز الصدع العملاق تحت الماء في المحيط الأطلسي

تحذير جديد: الاحترار العالمي يتسارع وقد نكسر حاجز 1.5 درجة قبل 2030

الصين تكشف عن ألياف كربون تفوق قوة الفولاذ بـ10 مرات

الجهاز المناعي يظهر دورا غير متوقع في صحة العظام

المزيد

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

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