Örtüşme (yeniden yazma terimi) - Overlap (term rewriting)

İçinde matematik, bilgisayar Bilimi ve mantık, üst üste gelmekindirim kurallarının bir özelliği olarak terim yeniden yazma sistemi, bir dizi farklı indirim kuralının bir indirgenebilir ifadeyi azaltmanın potansiyel olarak çelişkili yollarını belirttiği bir durumu açıklar; dönem.^[1]

Daha kesin olarak, eğer bir dizi farklı indirgeme kuralı sol taraftaki fonksiyon sembollerini paylaşırsa, örtüşme meydana gelebilir. Çoğu zaman, redex ve kendisiyle önemsiz bir örtüşmeyi düşünmüyoruz.

Örnekler

Aşağıdaki indirim kurallarıyla tanımlanan yeniden yazma sistemi terimini düşünün:

${displaystyle ho _ {1}: f (g (x), y) ightarrow y}$

${displaystyle ho _ {2}: g (x) ightarrow f (x, x)}$

Dönem ${displaystyle f (g (x), y)}$ ρ ile azaltılabilir₁ pes etmek y, ancak aynı zamanda ρ yoluyla da azaltılabilir₂ pes etmek ${displaystyle f (f (x, x), y).}$. Redex'in ${displaystyle g (x)}$ redekste bulunur ${displaystyle f (g (x), y)}$. Farklı redekslerin azaltılmasının sonucu, bir kritik çift; bu terim yeniden yazma sisteminden kaynaklanan kritik çift ${displaystyle (f (f (x, x), y), y)}$.

İkiden az indirim kuralıyla örtüşme meydana gelebilir.

Aşağıdaki indirim kuralı tarafından tanımlanan yeniden yazma sistemi terimini düşünün:

${displaystyle ho _ {1}: g (g (x)) ightarrow x}$

Dönem ${displaystyle g (g (g (x)))}$ örtüşen redekslere sahiptir ve bu, en içteki oluşumuna veya en dıştaki oluşumuna uygulanabilir. ${displaystyle g (g (x))}$ terim.

Referanslar

Bu matematiksel mantık ile ilgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.