Knuth–Bendix tamamlama algoritması - Knuth–Bendix completion algorithm

Knuth-Bendix tamamlama algoritması (adını Donald Knuth ve Peter Bendix) a, yarı karar algoritması bir dizi dönüştürmek için denklem (fazla açısından bir içine) birleşik terimi, yeniden sistemi . Algoritma başarılı olduğunda, belirtilen cebir için kelime problemini etkili bir şekilde çözer .

Buchberger'in Gröbner tabanlarını hesaplamak için kullandığı algoritma çok benzer bir algoritmadır. Bağımsız olarak geliştirilmiş olmasına rağmen, polinom halkaları teorisinde Knuth-Bendix algoritmasının somutlaştırılması olarak da görülebilir .

Tanıtım

Bir dizi E denklemi için, tümdengelimli kapanışı (⁎⟷E), herhangi bir sırada E'den denklemler uygulanarak türetilebilen tüm denklemlerin kümesidir . Resmi olarak, E ikili bir ilişki olarak kabul edilir , (⟶E) onun yeniden yazma kapanışıdır ve (⁎⟷E) denklik kapanışıdır (⟶E). Bir dizi R yeniden yazma kuralı için, tümdengelimli kapanışı (⁎⟶r ∘ ⁎⟵r), kelimenin tam anlamıyla eşit olana kadar her iki tarafa R soldan sağa kurallar uygulanarak doğrulanabilen tüm denklemlerin kümesidir . Resmi olarak, R yine ikili ilişki olarak görülür, (⟶r) onun yeniden yazma kapanışıdır, (⟵r) onun tersidir ve (⁎⟶r ∘ ⁎⟵r) Olan ilişkisi bileşimin kendi içinde dönüşlü geçişli kapakları (⁎⟶r ve ⁎⟵r).

Örneğin, E = {1⋅ x = X , X ^-1 ⋅ x = 1 olduğunda, ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z )} olan grup aksiyonları, türetme zinciri

a ^-1 ⋅( bir ⋅ b )   ⁎⟷E   ( a ⁻¹ ⋅ bir )⋅ b   ⁎⟷E   1⋅ b   ⁎⟷E   B

gösteriyor ki , bir ^-1 ⋅ ( bir ⋅ b ) ⁎⟷E b , E' nin tümdengelim kapanışının bir üyesidir . Eğer R = {1⋅ x → X , X ^-1 ⋅ x → 1, ( x ⋅ y ) ⋅ z → x ⋅ ( y ⋅ z )} bir "yeniden yazma kural" versiyonu E , türetme zincirleri

( a ⁻¹ ⋅ bir )⋅ b   ⁎⟶r   1⋅ b   ⁎⟶r   b       ve       b   ⁎⟵r   B

( a ⁻¹ ⋅ a )⋅ b olduğunu gösterin ⁎⟶r∘⁎⟵r b , R' s tümdengelim kapanışının bir üyesidir . Ancak, bir ⁻¹ ⋅( a ⋅ b ) elde etmenin bir yolu yoktur.⁎⟶r∘⁎⟵r b yukarıdakine benzer, çünkü ( x ⋅ y )⋅ z → x ⋅( y ⋅ z ) kuralının sağdan sola uygulanmasına izin verilmez.

Knuth-Bendix algoritması, terimler arasında bir E denklemleri kümesi ve tüm terimler kümesinde bir indirgeme sıralaması (>) alır ve E ile aynı tümdengelim kapanışına sahip olan birleşik ve sonlandırıcı bir terim yeniden yazma sistemi R oluşturmaya çalışır . E'den sonuçları kanıtlamak genellikle insan sezgisini gerektirirken, R'den sonuçları kanıtlamak gerekmez. Daha fazla ayrıntı için, bkz Confluence (Özet yeniden yazma) #Motivating örnekleri grup teorisi bir örnek kanıt sağlar, hem de kullanılarak gerçekleştirildi E izlenerek ve R .

Tüzük

Terimler arasında bir E denklem seti verildiğinde , onu eşdeğer bir yakınsak terim yeniden yazma sistemine dönüştürmek için aşağıdaki çıkarım kuralları kullanılabilir (mümkünse): Bunlar , tüm terimler kümesinde kullanıcı tarafından verilen bir indirgeme sıralamasına (>) dayanır. ; Bu tanımlayarak yeniden yazma kurallar kümesi üzerinde iyi kurulmuş sipariş (▻) için kaldırıldığında ( s → t ) ▻ ( l → r ) ise

• s >e L , ya
• s ve L olan anlamıyla benzer ve t > r .

Silmek	‹  E ∪{ s = s }	, R  ›	⊢	‹  E	, R  ›
oluştur	‹  E	, R ∪{ s → t } ›	⊢	‹  E	, R ∪{ s → u } ›	eğer t ⟶r sen
basitleştirin	‹  E ∪{ s = t }	, R  ›	⊢	‹  E ∪{ s = u }	, R  ›	eğer t ⟶r sen
oryantal	‹  E ∪{ s = t }	, R  ›	⊢	‹  E	, R ∪{ s → t } ›	eğer s > t
Yıkılmak	‹  E	, R ∪{ s → t } ›	⊢	‹  E ∪{ u = t }	, R  ›	eğer s ⟶r u by l → r ile ( s → t ) ▻ ( l → r )
Sonuç çıkarmak	‹  E	, R  ›	⊢	‹  E ∪{ s = t }	, R  ›	Eğer ( s , t ), a, kritik çifti arasında R

Örnek

E teoremi ispatından elde edilen aşağıdaki örnek çalıştırma, Knuth, Bendix (1970)'deki gibi (toplamsal) grup aksiyomlarının bir tamamlanmasını hesaplar. Bu kullanılarak, grup (nötr element 0, ters elemanları, birleşme) için üç başlangıç denklem ile başlar f(X,Y)için x + Y ve i(X)için - X . 10 yıldızlı denklemlerin, ortaya çıkan yakınsak yeniden yazma sistemini oluşturduğu ortaya çıktı. "pm" "kısaltmasıdır paramodulation uygulanması", anlamak . Kritik çift hesaplaması, denklemsel birim cümleleri için bir paramodülasyon örneğidir. "rw" yeniden yazma, oluşturma , daraltma ve basitleştirme uygulamasıdır . Denklemlerin yönlendirilmesi örtülü olarak yapılır ve kaydedilmez.

No		Lhs		Rh	Kaynak
1:	*	f(X,0)	=	x	initial("GROUP.lop", at_line_9_column_1)
2:	*	f(X,i(X))	=	0	initial("GROUP.lop", at_line_12_column_1)
3:	*	f(f(X,Y),Z)	=	f(X,f(Y,Z))	initial("GROUP.lop", at_line_15_column_1)
5:		f(X,Y)	=	f(X,f(0,Y))	öğleden sonra(3,1)
6:		f(X,f(Y,i(f(X,Y))))	=	0	öğleden sonra(2,3)
7:		f(0,Y)	=	f(X,f(i(X),Y))	öğleden sonra(3,2)
27:		f(X,0)	=	f(0,i(i(X)))	öğleden sonra(7,2)
36:		x	=	f(0,i(i(X)))	rw(27,1)
46:		f(X,Y)	=	f(X,i(i(Y)))	öğleden sonra(5,36)
52:	*	f(0,X)	=	x	rw(36,46)
60:	*	ben(0)	=	0	öğleden sonra(2,52)
63:		ben(i(X))	=	f(0,X)	öğleden sonra(46,52)
64:	*	f(X,f(i(X),Y))	=	Y	rw(7,52)
67:	*	ben(i(X))	=	x	rw(63,52)
74:	*	f(i(X),X)	=	0	öğleden sonra(2.67)
79:		f(0,Y)	=	f(i(X),f(X,Y))	öğleden sonra(3.74)
83:	*	Y	=	f(i(X),f(X,Y))	rw(79,52)
134:		f(i(X),0)	=	f(Y,i(f(X,Y)))	öğleden sonra(83,6)
151:		ben(X)	=	f(Y,i(f(X,Y)))	rw(134,1)
165:	*	f(i(X),i(Y))	=	ben(f(Y,X))	öğleden sonra(83,151)

Bu örneğin başka bir sunumu için ayrıca bkz. Word problemi (matematik) .

Grup teorisinde dize yeniden yazma sistemleri

Önemli bir olgu hesaplama grup teorisi elemanları veya kanonik etiketleri vermek için kullanılabilir dize yeniden yazma sistemlerdir kalan sınıfları a sonlu takdim grubun ürünleri olarak jeneratörler . Bu özel durum, bu bölümün odak noktasıdır.

Grup teorisinde motivasyon

Kritik çifti lemma bir terimdir yeniden yazma sistem olduğunu devletler lokal birleşik (ya zayıf kaynaşık) eğer ve tüm yalnızca kritik çiftleri yakınsak vardır. Ayrıca, bir (soyut) yeniden yazma sistemi güçlü bir şekilde normalleşiyorsa ve zayıf bir şekilde birleşiyorsa, o zaman yeniden yazma sisteminin birleşik olduğunu belirten Newman'ın lemması var . Dolayısıyla, güçlü normalleştirme özelliğini korurken tüm kritik çiftleri yakınsak olmaya zorlamak için yeniden yazma sistemi terimine kurallar ekleyebilirsek, bu, sonuçta ortaya çıkan yeniden yazma sistemini birleşik olmaya zorlayacaktır.

X'in sonlu bir üreteçler kümesi olduğu ve R'nin X üzerindeki bir tanımlayıcı ilişkiler kümesi olduğu sonlu olarak sunulan bir monoid düşünün . X ^* , X'teki tüm sözcüklerin kümesi olsun (yani X tarafından üretilen serbest monoid). R bağıntıları X* üzerinde bir denklik bağıntısı ürettiğinden, M'nin elemanlarının R altında X ^*' in denklik sınıfları olduğu düşünülebilir. Her bir sınıf için {w ₁ , w ₂ , ... } bir standart seçilmesi arzu edilir. temsilci w _k . Bu temsilci, sınıftaki her w _k kelimesi için kanonik veya normal form olarak adlandırılır . Her w _k için normal w _i biçimini belirlemek için hesaplanabilir bir yöntem varsa, o zaman kelime problemi kolayca çözülür. Birleştirilmiş bir yeniden yazma sistemi, kişinin tam olarak bunu yapmasına izin verir. ${\displaystyle M=\langla X\orta R\rangle }$

Kanonik bir formun seçimi teorik olarak keyfi bir şekilde yapılabilmesine rağmen, bu yaklaşım genellikle hesaplanabilir değildir. (Bir dil üzerinde bir denklik ilişkisinin sonsuz sayıda sonsuz sınıf üretebileceğini düşünün.) Eğer dil iyi sıralanmışsa, o zaman < sırası, minimal temsilciler tanımlamak için tutarlı bir yöntem verir, ancak bu temsilcilerin hesaplanması yine de mümkün olmayabilir. Özellikle, minimum temsilcileri hesaplamak için bir yeniden yazma sistemi kullanılıyorsa, sipariş < ayrıca şu özelliğe sahip olmalıdır:

A < B → XAY < XBY, tüm A,B,X,Y kelimeleri için

Bu özelliğe çeviri değişmezliği denir . Hem ötelemede değişmeyen hem de iyi sıralı olan bir sıraya indirgeme sırası denir .

Monoidin sunumundan, R bağıntıları tarafından verilen bir yeniden yazma sistemi tanımlamak mümkündür. Eğer A x B R'deyse, o zaman ya A < B, bu durumda B → A, yeniden yazma sisteminde bir kuraldır, aksi takdirde A > B ve A → B. < bir indirgeme sırası olduğundan, belirli bir W kelimesi azaltılabilir W > W_1 > ... > W_n burada W_n yeniden yazma sistemi altında indirgenemez. Ancak, her bir W _i  → W _i+1'de uygulanan kurallara bağlı olarak, W'nin iki farklı indirgenemez indirgemesi W _n  ≠ W' _{m elde etmek mümkündür} . Ancak, ilişkiler tarafından verilen yeniden yazma sistemi dönüştürülürse Knuth-Bendix algoritması aracılığıyla birleşik bir yeniden yazma sistemine dönüştürülürse, tüm indirgemelerin aynı indirgenemez kelimeyi, yani o kelimenin normal formunu üretmesi garanti edilir.

Sonlu olarak sunulan monoidler için algoritmanın açıklaması

Bize bir sunum verildiğini varsayalım , burada bir dizi üreteç ve yeniden yazma sistemini veren bir dizi ilişkidir . Ayrıca , (örneğin, shortlex order ) tarafından oluşturulan kelimeler arasında bir indirgeme sıralamasına sahip olduğumuzu varsayalım . içindeki her ilişki için , varsayalım . Böylece indirgeme seti ile başlıyoruz . ${\displaystyle \langle X\orta R\rangle }$${\görüntüleme stili X}$${\görüntüleme stili R}$${\görüntüleme stili <}$${\görüntüleme stili X}$${\displaystyle P_{i}=Q_{i}}$${\görüntüleme stili R}$${\displaystyle Q_{i}<P_{i}}$${\displaystyle P_{i}\rightarrow Q_{i}}$

İlk olarak, eğer herhangi bir ilişki azaltılabilirse, yerine ve indirimlerle değiştirin . ${\displaystyle P_{i}=Q_{i}}$${\görüntüleme stili P_{i}}$${\ Displaystyle Q_ {i}}$

Ardından, olası çakışma istisnalarını ortadan kaldırmak için daha fazla azaltma (yani yeniden yazma kuralları) ekliyoruz. Bunu varsayalım ve üst üste binelim. ${\görüntüleme stili P_{i}}$${\görüntüleme stili P_{j}}$

1. Durum 1: ya ön eki son ekine eşittir ya da tam tersi. İlk durumda, yazabiliriz ve ; ikinci durumda ve .${\görüntüleme stili P_{i}}$${\görüntüleme stili P_{j}}$${\displaystyle P_{i}=BC}$${\displaystyle P_{j}=AB}$${\displaystyle P_{i}=AB}$${\displaystyle P_{j}=BC}$
2. Durum 2: ya tamamen (çevrili) içinde bulunur ya da tam tersi. İlk durumda, yazabiliriz ve ; ikinci durumda ve .${\görüntüleme stili P_{i}}$${\görüntüleme stili P_{j}}$${\görüntüleme stili P_{i}=B}$${\displaystyle P_{j}=ABC}$${\displaystyle P_{i}=ABC}$${\görüntüleme stili P_{j}=B}$

Kelimeyi önce kullanarak , sonra önce kullanarak azaltın . Sonuçları sırasıyla çağırın . Eğer , o zaman izdihamın başarısız olabileceği bir örneğimiz var. Bu nedenle, bir azalma eklemek için . ${\görüntüleme stili ABC}$${\görüntüleme stili P_{i}}$${\görüntüleme stili P_{j}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1}\neq r_{2}}$${\displaystyle \max r_{1},r_{2}\rightarrow \min r_{1},r_{2}}$${\görüntüleme stili R}$

öğesine bir kural ekledikten sonra , indirgenebilir sol kenarları olabilecek tüm kuralları kaldırın (bu tür kuralların diğer kurallarla kritik çiftleri olup olmadığını kontrol ettikten sonra). ${\görüntüleme stili R}$${\görüntüleme stili R}$

Üst üste binen tüm sol taraflar kontrol edilene kadar prosedürü tekrarlayın.

Örnekler

Bir sonlandırma örneği

Monoidi düşünün:

${\displaystyle \langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle }$.

Biz kullanmak shortlex düzeni . Bu sonsuz bir monoiddir, ancak yine de Knuth-Bendix algoritması kelime problemini çözebilir.

Bu nedenle başlangıçtaki üç indirgememiz

${\displaystyle x^{3}\rightarrow 1}$

( 1 )

${\ Displaystyle y^{3}\rightarrow 1}$

( 2 )

${\görüntüleme stili (xy)^{3}\rightarrow 1}$.

( 3 )

Soneki (yani ) öğesinin önekidir , bu nedenle kelimeyi düşünün . ( 1 ) kullanarak azaltarak elde ederiz . ( 3 ) kullanarak azaltarak elde ederiz . Dolayısıyla, indirgeme kuralını vererek elde ederiz.${\görüntüleme stili x^{3}}$${\görüntüleme stili x}$${\görüntüleme stili (xy)^{3}=xyxyxy}$${\displaystyle x^{3}yxyxy}$${\görüntüleme stili yxyxy}$${\görüntüleme stili x^{2}}$${\displaystyle yxyxy=x^{2}}$

${\displaystyle yxyxy\rightarrow x^{2}}$.

( 4 )

Benzer şekilde, ( 2 ) ve ( 3 ) kullanarak ve azaltarak , elde ederiz . Dolayısıyla azalma ${\görüntüleme stili xyxyxy^{3}}$${\displaystyle xyxyx=y^{2}}$

${\displaystyle xyxyx\rightarrow y^{2}}$.

( 5 )

Bu kuralların ikisi de geçersizdir ( 3 ), bu yüzden onu kaldırıyoruz.

Ardından, ( 1 ) ve ( 5 ) çakıştırarak düşünün . Azaltarak elde ederiz , yani kuralı ekliyoruz ${\displaystyle x^{3}yxyx}$${\displaystyle yxyx=x^{2}y^{2}}$

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$.

( 6 )

( 1 ) ve ( 5 ) üst üste binerek düşünürsek , kuralı ekliyoruz ${\görüntüleme stili xyxyx^{3}}$${\displaystyle xyxy=y^{2}x^{2}}$

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

( 7 )

Bu eski kurallar ( 4 ) ve ( 5 ) , bu yüzden onları kaldırıyoruz.

Şimdi, yeniden yazma sistemi ile kaldık

${\displaystyle x^{3}\rightarrow 1}$

( 1 )

${\ Displaystyle y^{3}\rightarrow 1}$

( 2 )

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$

( 6 )

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

( 7 )

Bu kuralların örtüşmelerini kontrol ettiğimizde, olası bir birleşme hatası bulmuyoruz. Bu nedenle, birleşik bir yeniden yazma sistemimiz var ve algoritma başarıyla sonlandırılıyor.

Sonu olmayan bir örnek

Jeneratörlerin sırası, Knuth-Bendix tamamlamasının sona erip sonlanmayacağını önemli ölçüde etkileyebilir. Örnek olarak, monoid sunumuna göre serbest Abelian grubunu düşünün :

${\displaystyle \langle x,y,x^{-1},y^{-1}\,|\,xy=yx,xx^{-1}=x^{-1}x=yy^{- 1}=y^{-1}y=1\rangle .}$

Sözlükbilimsel sıraya göre Knuth-Bendix tamamlaması yakınsak bir sistemle tamamlanır, ancak uzunluk-sözlükbilimsel sıra göz önüne alındığında, bu son sıra ile uyumlu sonlu yakınsak sistemler olmadığı için bitirmez. ${\displaystyle x<x^{-1}<y<y^{-1}}$${\displaystyle x<y<x^{-1}<y^{-1}}$

genellemeler

Knuth-Bendix başarılı olmazsa, ya sonsuza kadar çalışacak ya da yönlendirilemez bir denklemle (yani yeniden yazma kuralına dönüşemeyecek bir denklem) karşılaştığında başarısız olacaktır. Geliştirilmiş arızasız tamamlanması unorientable denklemler üzerinde başarısız bir sağlar olmaz yarı karar prosedürü kelime sorun.

Aşağıda listelenen Heyworth ve Wensley tarafından makalede tartışılan kayıtlı yeniden yazma kavramı, ilerledikçe yeniden yazma sürecinin bir miktar kaydedilmesine veya günlüğe kaydedilmesine izin verir. Bu, grupların sunumları için ilişkiler arasındaki kimlikleri hesaplamak için kullanışlıdır.

Referanslar

• D. Knuth; P. Bendix (1970). J. Leech (ed.). Evrensel Cebirlerde Basit Kelime Problemleri (PDF) . Bergama Basın. s. 263–297.
• Gerard Huet (1981). "Knuth-Bendix Tamamlama Algoritmasının Tam Doğruluğunun Kanıtı" (PDF) . J. Bilgisayar. Sist. Sci . 23 (1): 11–21. doi : 10.1016/0022-0000(81)90002-7 .
• C. Simler. 'Sınırlı olarak sunulan gruplarla hesaplamalar.' Cambridge, 1994.
• Anne Heyworth ve CD Wensley. " Günlük yeniden yazma ve ilgililer arasında kimlikler ." Gruplar St. Andrews 2001 Oxford'da. Cilt Ben, 256-276, Londra Matematik. Soc. Ders Notu Ser., 304, Cambridge Üniv. Basın, Cambridge, 2003.

Dış bağlantılar

• Weisstein, Eric W. "Knuth-Bendix Tamamlama Algoritması" . Matematik Dünyası .
• Knuth-Bendix Tamamlama Görselleştiricisi