Confluence (soyut yeniden yazma) - Confluence (abstract rewriting)

Resim 1: İsim izdiham esinlenmiştir coğrafya yani iki su kütlesinin buluşması.

Bilgisayar biliminde, izdiham mülkiyetidir yeniden yazma aynı sonucu vermek için böyle bir sistemdeki hangi terimlerin birden fazla şekilde yeniden yazılabileceğini açıklayan sistemler. Bu makale, en soyut ortamdaki özellikleri açıklar. soyut yeniden yazma sistemi.

Motive edici örnekler

Temel aritmetiğin olağan kuralları, soyut bir yeniden yazma sistemini oluşturur.Örneğin, (11 + 9) × (2 + 4) ifadesi, sol veya sağ parantezden başlayarak değerlendirilebilir; ancak her iki durumda da aynı sonuç Bu, aritmetik yeniden yazma sisteminin birleşik bir sistem olduğunu gösterir.

Her birinin aşağıdaki ispatından ikinci, daha soyut bir örnek elde edilir. grup eşit olan eleman ters tersi:^[1]

Grup aksiyomları
A1	1 ⋅ a	= a
A2	a⁻¹ ⋅ a	= 1
A3	(a ⋅ b) ⋅ c	= a ⋅ (b ⋅ c)

Kanıtı R4: a⁻¹⋅(a⋅b) = b
	a⁻¹ ⋅ (a ⋅ b)
=	(a⁻¹ ⋅ a) ⋅ b	A3 (r) tarafından
=	1 ⋅ b	A2 tarafından
=	b	A1 tarafından

Kanıtı R6: (a⁻¹)⁻¹ ⋅ 1 = a
	(a⁻¹)⁻¹ ⋅ 1
=	(a⁻¹)⁻¹ ⋅ (a⁻¹ ⋅ a)	A2 (r) tarafından
=	a	R4 tarafından

Kanıtı **R10**: (a⁻¹)⁻¹ ⋅ b = a ⋅ b
	(a⁻¹)⁻¹ ⋅ b
=	(a⁻¹)⁻¹ ⋅ (a⁻¹ ⋅ (a ⋅ b))	R4 (r) tarafından
=	a ⋅ b	R4 tarafından

Kanıtı **R11**: a ⋅ 1 = a
	a ⋅ 1
=	(a⁻¹)⁻¹ ⋅ 1	R10 (r) tarafından
=	a	R6 tarafından

Kanıtı **R12**: (a⁻¹)⁻¹ = a
	(a⁻¹)⁻¹
=	(a⁻¹)⁻¹ ⋅ 1	R11 (r) tarafından
=	a	R6 tarafından

Bu ispat, verilen grup aksiyomları A1-A3'ten başlar ve her biri daha öncekileri kullanan beş R4, R6, R10, R11 ve R12 önermesi oluşturur ve R12 ana teoremdir. İspatlardan bazıları, A2 aksiyomunu tersten uygulamak ve böylece "1" i "için" yeniden yazmak gibi, yaratıcı değilse de bariz olmayan adımlar gerektirir.a⁻¹ ⋅ a ", R6'nın ispatının ilk adımında. terim yeniden yazma teorisi bir bilgisayar programı bir yana, deneyimsiz bir insan tarafından bulunması zor olan bu tür adımlara olan ihtiyacı ortadan kaldırmaktı.

Eğer bir terim yeniden yazma sistemi dır-dir birbirine karışan ve sonlandırma, iki ifade arasında eşitliği kanıtlamak için basit bir yöntem vardır (a.k.a. şartlar ) s ve t: İle başlayan seşitlikler uygula^{[not 1]} mümkün olduğunca uzun süre soldan sağa, sonunda bir terim s ’.Den elde edin t bir terim t ’ benzer şekilde. s ’ ve t ’ tam anlamıyla katılıyorum o zaman s ve t Eşit olduğu (şaşırtıcı değil) kanıtlanmıştır. s ve t eşit olamaz, yani herhangi iki terim s ve t bunun eşit olduğu kanıtlanabilir, bu yöntemle öyle olabilir.

Bu yöntemin başarısı, yeniden yazma kurallarının uygulanacağı belirli bir karmaşık düzene bağlı değildir. izdiham herhangi bir kural uygulaması dizisinin sonunda aynı sonuca yol açmasını sağlar ( sonlandırma özellik, herhangi bir dizinin sonunda bir sona ulaşmasını sağlar).^[2] Bu nedenle, bazı eşitlik teorileri için birleşik ve sonlandırıcı bir terim yeniden yazma sistemi sağlanabilirse,^{[not 2]} eşitlik terimlerini kanıtlamak için hiçbir yaratıcılık gerekmez; bu görev dolayısıyla bilgisayar programlarına uygun hale gelir. Modern yaklaşımlar daha genel işler soyut yeniden yazma sistemleri ziyade dönem yeniden yazma sistemleri; ikincisi, ilkinin özel bir durumudur.

Genel durum ve teori

Resim 2: Bu diyagramda,

a

ikisine de azalır

b

veya

c

sıfır veya daha fazla yeniden yazma adımında (yıldız işaretiyle gösterilir). Yeniden yazma ilişkisinin birleşik olması için, her iki indirgeme de bazı ortak noktalara indirilmelidir.

d

.

Yeniden yazma sistemi şu şekilde ifade edilebilir: Yönlendirilmiş grafik düğümlerin ifadeleri ve kenarların yeniden yazmaları temsil ettiği. Yani, örneğin, eğer ifade a yeniden yazılabilir b, sonra şunu söyleriz b bir azaltmak nın-nin a (alternatif olarak, a azaltır bveya a bir genişleme nın-nin b). Bu, ok gösterimi kullanılarak temsil edilir; a → b belirtir a azaltır b. Sezgisel olarak, bu, karşılık gelen grafiğin, a -e b.

İki grafik düğümü arasında bir yol varsa c ve d, sonra bir indirgeme dizisi. Yani, örneğin, eğer c → c’ → c’’ → ... → d’ → do zaman yazabiliriz c ∗→ dbir indirgeme dizisinin varlığını gösteren c -e d. Resmen, ∗→ ... dönüşlü geçişli kapanma arasında →. Önceki paragraftaki örneği kullanarak, (11 + 9) × (2 + 4) → 20 × (2 + 4) ve 20 × (2 + 4) → 20 × 6, yani (11 + 9) × ( 2 + 4) ∗→ 20×6.

Bu kurulduğunda, izdiham aşağıdaki gibi tanımlanabilir. a ∈ S tüm çiftler için birleşik olarak kabul edilir b, c ∈ S öyle ki a ∗→ b ve a ∗→ cvar bir d ∈ S ile b ∗→ d ve c ∗→ d. Eğer her a ∈ S birbirine karışmışsa, → birbirine karışmış veya Church-Rosser özelliği. Bu özelliğe bazen elmas özelliği, sağda gösterilen diyagramın şeklinden sonra. Bazı yazarlar terimi rezerve eder elmas özelliği her yerde tek indirimlerle diyagramın bir varyantı için; yani, her zaman a → b ve a → c, orada olmalı d öyle ki b → d ve c → d. Tek indirgemeli varyant, çoklu indirgemeli olandan kesinlikle daha güçlüdür.

Yerel izdiham

Resim 3: Döngüsel, yerel olarak birleşik, ancak küresel olarak birleşik olmayan yeniden yazma sistemi^[3]

Resim 4: Sonsuz döngüsel olmayan, yerel olarak birleşik, ancak küresel olarak birleşik olmayan yeniden yazma sistemi^[3]

Bir element a ∈ S yerel olarak (veya zayıf bir şekilde) birbirine karıştığı söylenirse b, c ∈ S ile a → b ve a → c var d ∈ S ile b ∗→ d ve c ∗→ d. Eğer her a ∈ S yerel olarak birleşik ise → yerel olarak (veya zayıf bir şekilde) birleşmiş olarak adlandırılır veya zayıf Church-Rosser mülkü. Bu izdihamdan farklıdır b ve c azaltılmalı a tek adımda. Buna benzer şekilde, izdiham bazen şu şekilde anılır: küresel izdiham.

İlişki ∗→, indirgeme dizileri için bir notasyon olarak sunulan, kendi başına bir yeniden yazma sistemi olarak görülebilir; dönüşlü geçişli kapanma nın-nin →. Bir indirgeme dizileri dizisi yine bir indirgeme dizisi olduğundan (veya eşdeğer olarak, çünkü refleksif geçişli kapanmanın oluşturulması etkisiz ), ∗∗→ = ∗→. Bunu takip eder → ancak ve ancak ∗→ yerel olarak birbirine karışıyor.

Yeniden yazma sistemi, (küresel olarak) birleşik olmadan yerel olarak birbirine karışabilir. Örnekler resim 3 ve 4'te gösterilmiştir. Ancak, Newman lemması yerel olarak birleşik bir yeniden yazma sisteminin sonsuz indirgeme dizilerine sahip olmadığını belirtir (bu durumda, sonlandırma veya şiddetle normalleştirme), daha sonra küresel olarak birbirine karışır.

Yarı izdiham

Yerel birleşme tanımı, yalnızca tek bir yeniden yazma adımında belirli bir öğeden ulaşılan öğelerin dikkate alınmasıyla küresel birleşme tanımından farklıdır. Tek bir adımda ulaşılan bir öğeyi ve rastgele bir sırayla ulaşılan başka bir öğeyi göz önünde bulundurarak, yarı-izdihamın ara kavramına ulaşıyoruz: a ∈ S hepsi için yarı-birleşik olduğu söyleniyor b, c ∈ S ile a → b ve a ∗→ c var d ∈ S ile b ∗→ d ve c ∗→ d; eğer her biri a ∈ S yarı-birleşik, biz diyoruz ki → yarı-birleşik.

Yarı-birleşik bir elemanın birleşik olması gerekmez, ancak yarı-birleşik bir yeniden yazma sistemi zorunlu olarak birleşiktir ve birleşik bir sistem önemsiz bir şekilde yarı-birleşiktir.

Güçlü izdiham

Güçlü birleşme, bir yeniden yazma sisteminin küresel olarak birbirine karıştığı sonucuna varmamıza olanak tanıyan yerel izdihamın başka bir varyasyonudur. Bir element a ∈ S herkes için ise güçlü bir şekilde birleştiği söyleniyor b, c ∈ S ile a → b ve a → c var d ∈ S ile b ∗→ d ya da c → d veya c = d; eğer her biri a ∈ S güçlü bir şekilde birleşik, biz diyoruz ki → güçlü bir şekilde birleşir.

Birleşik bir öğenin güçlü bir şekilde birbirine karışması gerekmez, ancak güçlü bir şekilde birleşen bir yeniden yazma sistemi zorunlu olarak birleşiktir.

Birleşen sistem örnekleri

Polinomların indirgenmesi modülo bir ideal, birinin bir ile çalışması şartıyla birleşik bir yeniden yazma sistemidir. Gröbner temeli.
Matsumoto teoremi örgü ilişkilerinin izdihamını takip eder.
λ-terimlerinin β-azaltılması, Church-Rosser teoremi.

Ayrıca bakınız

Notlar

^ sonra aradı kuralları yeniden yaz soldan sağa yönelimini vurgulamak için
^ Knuth – Bendix tamamlama algoritması belirli bir denklem setinden böyle bir sistemi hesaplamak için kullanılabilir. Böyle bir sistem, ör. gruplar için gösterilir İşte önermeleri tutarlı bir şekilde numaralandırılmıştır. Bunu kullanarak, örn. R6, R11 ve R12'yi herhangi bir sırayla (a⁻¹)⁻¹⋅1 elde etmek için a.; başka hiçbir kural uygulanamaz.

Referanslar

Dönem Yeniden Yazım Sistemleri, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.
Dönem Yeniden Yazımı ve Hepsi, Franz Baader ve Tobias Nipkow, Cambridge University Press, 1998

^ K. H. Bläsius ve H.-J. Bürckert, ed. (1992). Deduktionsssysteme. Oldenbourg. s. 291.; burada: s. 134; aksiyom ve önerme adları orijinal metni takip eder
^ Yeni Bir Bilim Türü [1]
^ ^a ^b N. Dershowitz ve J.-P. Jouannaud (1990). "Yeniden Yazma Sistemleri". Jan van Leeuwen'de (ed.). Biçimsel Modeller ve Anlambilim. Teorik Bilgisayar Bilimi El Kitabı. B. Elsevier. s. 243–320. ISBN 0-444-88074-7. Burada: s. 268, Şek. 2a + b.

Dış bağlantılar

Weisstein, Eric W. "Confluent". MathWorld.

[2] sonra aradı kuralları yeniden yaz soldan sağa yönelimini vurgulamak için

[4] Knuth – Bendix tamamlama algoritması belirli bir denklem setinden böyle bir sistemi hesaplamak için kullanılabilir. Böyle bir sistem, ör. gruplar için gösterilir İşte önermeleri tutarlı bir şekilde numaralandırılmıştır. Bunu kullanarak, örn. R6, R11 ve R12'yi herhangi bir sırayla (a⁻¹)⁻¹⋅1 elde etmek için a.; başka hiçbir kural uygulanamaz.

[1] K. H. Bläsius ve H.-J. Bürckert, ed. (1992). Deduktionsssysteme. Oldenbourg. s. 291.; burada: s. 134; aksiyom ve önerme adları orijinal metni takip eder

[NKS_note_d-3] Yeni Bir Bilim Türü [1]

[Dershowitz.Jouannaud.1990.Fig2-5] N. Dershowitz ve J.-P. Jouannaud (1990). "Yeniden Yazma Sistemleri". Jan van Leeuwen'de (ed.). Biçimsel Modeller ve Anlambilim. Teorik Bilgisayar Bilimi El Kitabı. B. Elsevier. s. 243–320. ISBN 0-444-88074-7. Burada: s. 268, Şek. 2a + b.

[1]

[not 1]

[2]

[not 2]

[3]