Anti-birleşme (bilgisayar bilimi) - Anti-unification (computer science) - Wikipedia

Anti-birleşme verilen iki sembolik ifadede ortak olan bir genelleme oluşturma sürecidir. De olduğu gibi birleşme, hangi ifadelere (terimler de denir) izin verildiğine ve hangi ifadelerin eşit kabul edildiğine bağlı olarak birkaç çerçeve ayırt edilir. Bir ifadede işlevleri temsil eden değişkenlere izin veriliyorsa, işleme "yüksek düzey birleşme önleme", aksi takdirde "birinci dereceden birleşme önleme" denir. Genellemenin her bir girdi ifadesine tam anlamıyla eşit bir örneğe sahip olması gerekiyorsa, işlem "sözdizimsel birleşme karşıtı", aksi takdirde "E-birleşme karşıtı" veya "birleşme karşıtı modulo teorisi" olarak adlandırılır.

Bir birleşme önleme algoritması, verilen ifadeler için eksiksiz ve asgari bir genelleme kümesi, yani sırasıyla tüm genellemeleri kapsayan ve artık üye içermeyen bir küme hesaplamalıdır. Çerçeveye bağlı olarak, eksiksiz ve minimum bir genelleme kümesi bir, sonlu çok veya muhtemelen sonsuz sayıda üyeye sahip olabilir veya hiç mevcut olmayabilir;^{[not 1]} her halükarda önemsiz bir genelleme olduğu için boş olamaz. Birinci dereceden sözdizimsel birleşme önleme için, Gordon Plotkin^[1][2] "en az genel genelleme" (lgg) denen şeyi içeren eksiksiz ve minimum tekil genelleme kümesini hesaplayan bir algoritma verdi.

Anti-birleşme ile karıştırılmamalıdır ayrışma. İkincisi, sistemleri çözme süreci anlamına gelir. eşitsizlikler Bu, değişkenler için, verilen tüm eşitsizliklerin karşılanacağı şekilde değerler bulmaktır.^{[not 2]} Bu görev genellemeler bulmaktan oldukça farklıdır.

Önkoşullar

Resmi olarak, bir anti-birleşme yaklaşımı,

• Sonsuz bir küme V nın-nin değişkenler. Üst düzey birleşme önleme için, seçmek uygundur V kümesinden ayrık lambda-vadeli bağlı değişkenler.
• Bir set T nın-nin şartlar öyle ki V ⊆ T. Birinci derece ve daha üst düzey birleşme önleme için, T genellikle kümesidir birinci dereceden şartlar (değişken ve fonksiyon sembollerinden oluşturulan terimler) ve lambda terimleri (bazı yüksek dereceli değişkenleri içeren terimler) sırasıyla.
• Bir denklik ilişkisi ${ displaystyle equiv}$ açık ${ displaystyle T}$, hangi terimlerin eşit kabul edildiğini gösterir. Daha yüksek düzeyde birleşme önleme için, genellikle ${ displaystyle t equiv u}$ Eğer ${ displaystyle t}$ ve ${ displaystyle u}$ vardır alfa eşdeğeri. Birinci dereceden E-birleşme önleme için, ${ displaystyle equiv}$ belirli işlev sembolleri hakkındaki arka plan bilgisini yansıtır; örneğin, eğer ${ displaystyle oplus}$ değişmeli olarak kabul edilir, ${ displaystyle t equiv u}$ Eğer ${ displaystyle u}$ elde edilen sonuçlar ${ displaystyle t}$ argümanlarını değiştirerek ${ displaystyle oplus}$ bazı (muhtemelen tüm) olaylarda.^{[not 3]} Hiç bir arka plan bilgisi yoksa, sadece kelime anlamıyla veya sözdizimsel olarak aynı terimler eşit kabul edilir.

Birinci dereceden terim

Bir set verildi ${ displaystyle V}$ değişken semboller, bir set ${ displaystyle C}$ sabit semboller ve kümeler ${ displaystyle F_ {n}}$ nın-nin ${ displaystyle n}$-her doğal sayı için operatör sembolleri olarak da adlandırılan işlev sembolleri ${ displaystyle n geq 1}$, (sıralanmamış birinci dereceden) terimler kümesi ${ displaystyle T}$ dır-dir yinelemeli olarak tanımlanmış aşağıdaki özelliklere sahip en küçük küme olmak:^[3]

• her değişken sembol bir terimdir: V ⊆ T,
• her sabit sembol bir terimdir: C ⊆ T,
• her n şartlar t₁,…,t_n, ve hepsi n-ary işlev sembolü f ∈ F_n, daha geniş bir terim ${ displaystyle f (t_ {1}, ldots, t_ {n})}$ inşa edilebilir.

Örneğin, eğer x ∈ V değişken bir semboldür, 1 ∈ C sabit bir semboldür ve ∈ ekleyin F₂ bir ikili fonksiyon sembolüdür, o zaman x ∈ T, 1 ∈ Tve (dolayısıyla) ekle (x,1) ∈ T sırasıyla birinci, ikinci ve üçüncü dönem inşa kuralına göre. İkinci terim genellikle şöyle yazılır x+1, kullanma Infix gösterimi ve rahatlık için daha yaygın operatör sembolü +.

Daha yüksek dereceli terim

ikame

Bir ikame bir haritalama ${ displaystyle sigma: V longrightarrow T}$ değişkenlerden terimlere; gösterim ${ displaystyle {x_ {1} mapsto t_ {1}, ldots, x_ {k} mapsto t_ {k} }}$ her değişkeni eşleştiren bir ikame eşlemesini ifade eder ${ displaystyle x_ {i}}$ terim ${ displaystyle t_ {i}}$, için ${ displaystyle i = 1, ldots, k}$ve diğer tüm değişkenler kendisine. Bu ikamenin bir terime uygulanması t sonek gösteriminde şu şekilde yazılmıştır: ${ displaystyle t {x_ {1} mapsto t_ {1}, ldots, x_ {k} mapsto t_ {k} }}$; her değişkenin her oluşumunu (aynı anda) değiştirmek anlamına gelir ${ displaystyle x_ {i}}$ dönem içinde t tarafından ${ displaystyle t_ {i}}$. Sonuç tσ bir ikame uygulama σ bir terime t denir örnek o terimin tBirinci dereceden bir örnek olarak, ikamenin uygulanması ${ displaystyle {x mapsto h (a, y), z mapsto b }}$ terim

f(	x	, a, g(	z	), y)	verim
f(	h(a,y)	, a, g(	b	), y)	.

Genelleme, uzmanlaşma

Eğer bir terim ${ displaystyle t}$ bir terime eşdeğer bir örneğe sahiptir ${ displaystyle u}$yani, eğer ${ displaystyle t sigma equiv u}$ biraz ikame için ${ displaystyle sigma}$, sonra ${ displaystyle t}$ denir daha genel -den ${ displaystyle u}$, ve ${ displaystyle u}$ denir daha özel veya içerilen tarafından, ${ displaystyle t}$. Örneğin, ${ displaystyle x oplus a}$ daha geneldir ${ displaystyle a oplus b}$ Eğer ${ displaystyle oplus}$ dır-dir değişmeli, o zamandan beri ${ displaystyle (x oplus a) {x mapsto b } = b oplus a equiv a oplus b}$.

Eğer ${ displaystyle equiv}$ terimlerin birebir (sözdizimsel) özdeşliğidir, bir terim hem daha genel hem de diğerinden daha özel olabilir, ancak her iki terim de sözdizimsel yapılarında değil, yalnızca değişken adlarında farklıysa; bu tür terimler denir varyantlarveya yeniden adlandırmalar Birbirinden. Örneğin, ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$ bir çeşididir ${ displaystyle f (x_ {2}, a, g (z_ {2}), y_ {2})}$, dan beri ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1}) {x_ {1} mapsto x_ {2}, y_ {1} mapsto y_ {2}, z_ {1} mapsto z_ {2} } = f (x_ {2}, a, g (z_ {2}), y_ {2})}$ ve ${ displaystyle f (x_ {2}, a, g (z_ {2}), y_ {2}) {x_ {2} mapsto x_ {1}, y_ {2} mapsto y_ {1}, z_ {2} mapsto z_ {1} } = f (x_ {1}, a, g (z_ {1}), y_ {1})}$.Ancak, ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$ dır-dir değil bir varyantı ${ displaystyle f (x_ {2}, a, g (x_ {2}), x_ {2})}$, çünkü hiçbir ikame ikinci terimi birincisine dönüştüremez, ancak ${ displaystyle {x_ {1} mapsto x_ {2}, z_ {1} mapsto x_ {2}, y_ {1} mapsto x_ {2} }}$ ters yöne ulaşır. İkinci terim, bu nedenle, birincisinden daha özeldir.

Bir ikame ${ displaystyle sigma}$ dır-dir daha özel veya içerilen bir ikame ${ displaystyle tau}$ Eğer ${ displaystyle x sigma}$ daha özel ${ displaystyle x tau}$ her değişken için ${ displaystyle x}$.Örneğin, ${ displaystyle {x mapsto f (u), y mapsto f (f (u)) }}$ daha özel ${ displaystyle {x mapsto z, y mapsto f (z) }}$, dan beri ${ displaystyle f (u)}$ ve ${ displaystyle f (f (u))}$ daha özel ${ displaystyle z}$ ve ${ displaystyle f (z)}$, sırasıyla.

Anti-birleşme sorunu, genelleme seti

Bir anti-birleşme sorunu bir çift ${ displaystyle langle t_ {1}, t_ {2} rangle}$ terim. bir terim ${ displaystyle t}$ ortak genellemeveya anti-birleştirici, nın-nin ${ displaystyle t_ {1}}$ ve ${ displaystyle t_ {2}}$ Eğer ${ displaystyle t sigma _ {1} equiv t_ {1}}$ ve ${ displaystyle t sigma _ {2} equiv t_ {2}}$ bazı ikameler için ${ displaystyle sigma _ {1}, sigma _ {2}}$Belirli bir anti-birleşme problemi için bir set ${ displaystyle S}$ anti-birleştiricilerin sayısı tamamlayınız her genelleme bir terimi kapsıyorsa ${ displaystyle t S olarak}$; set ${ displaystyle S}$ denir en az üyelerinden hiçbiri başka birini kapsamıyorsa.

Birinci dereceden sözdizimsel anti-birleşme

Birinci dereceden sözdizimsel birleşme karşıtı çerçeve, ${ displaystyle T}$ set olmak birinci dereceden şartlar (belirli bir sette ${ displaystyle V}$ değişkenlerin ${ displaystyle C}$ sabitlerin ve ${ displaystyle F_ {n}}$ nın-nin ${ displaystyle n}$-ary işlev sembolleri) ve açık ${ displaystyle equiv}$ olmak sözdizimsel eşitlikBu çerçevede, her bir anti-birleşme sorunu ${ displaystyle langle t_ {1}, t_ {2} rangle}$ tam ve açıkça minimum düzeyde Singleton çözüm seti ${ displaystyle {t }}$. Üyesi ${ displaystyle t}$ denir en az genel genelleme (lgg) problemin sözdizimsel olarak eşit bir örneğine sahip ${ displaystyle t_ {1}}$ ve bir diğeri sözdizimsel olarak eşittir ${ displaystyle t_ {2}}$Herhangi bir genel genelleme ${ displaystyle t_ {1}}$ ve ${ displaystyle t_ {2}}$ alt bölümler ${ displaystyle t}$Lgg, varyantlara kadar benzersizdir: if ${ displaystyle S_ {1}}$ ve ${ displaystyle S_ {2}}$ aynı sözdizimsel birleşme önleme sorununun hem eksiksiz hem de minimum çözüm kümeleridir, bu durumda ${ displaystyle S_ {1} = {s_ {1} }}$ ve ${ displaystyle S_ {2} = {s_ {2} }}$ bazı terimler için ${ displaystyle s_ {1}}$ ve ${ displaystyle s_ {2}}$, bunlar yeniden adlandırmalar birbirinden.

Plotkin^[1][2] verilen iki terimin lgg'sini hesaplamak için bir algoritma vermiştir. hedef haritalama ${ displaystyle phi: T times T longrightarrow V}$yani her çifti atayan bir eşleme ${ displaystyle s, t}$ terimlerin kendi değişkenleri ${ displaystyle phi (s, t)}$, öyle ki hiçbir çift aynı değişkeni paylaşmaz.^{[not 4]}Algoritma iki kuraldan oluşur:

${ displaystyle f (s_ {1}, noktalar, s_ {n}) sqcup f (t_ {1}, ldots, t_ {n})}$	${ displaystyle rightsquigarrow}$	${ displaystyle f (s_ {1} sqcup t_ {1}, ldots, s_ {n} sqcup t_ {n})}$
${ displaystyle s sqcup t}$	${ displaystyle rightsquigarrow}$	${ displaystyle phi (s, t)}$	önceki kural geçerli değilse

Örneğin, ${ displaystyle (0 * 0) sqcup (4 * 4) rightsquigarrow (0 sqcup 4) * (0 sqcup 4) rightsquigarrow phi (0,4) * phi (0,4) rightsquigarrow x * x}$; bu en az genel genelleme, her iki girdinin de kare sayı olmasının ortak özelliğini yansıtır.

Plotkin, algoritmasını kullanarak "göreceli en az genel genelleme (rlgg) "birinci dereceden mantıkta iki cümle kümesinin temeli Golem yaklaşım endüktif mantık programlama.

Birinci dereceden anti-birleşme modülo teorisi

Bu bölüm genişlemeye ihtiyacı var ile: aşağıdaki makalelerden alınan ana sonuçları açıklayın, yaklaşımlarını birbirleriyle ilişkilendirin. Yardımcı olabilirsiniz ona eklemek. (Haziran 2020)

• Jacobsen, Erik (Haziran 1991), Birleşme ve Birleşmeyi Önleme (PDF), Teknik rapor
• Østvold, Bjarte M. (Nisan 2004), Anti-Birleşmenin İşlevsel Bir Yeniden İnşası (PDF), NR Note, DART / 04/04, Norveç Bilgi İşlem Merkezi
• Boytcheva, Svetla; Markov, Zdravko (2002). "Göreli Çıkarım Altında En Az Genellemeyi Teşvik Etmek İçin Bir Algoritma" (PDF). Alıntı dergisi gerektirir | günlük = (Yardım)
• Kutsia, Temur; Levy, Jordi; Villaret, Mateu (2014). "Sıralanmamış Koşullar ve Korumalar için Birleşmeyi Önleme" (PDF). Otomatik Akıl Yürütme Dergisi. 52 (2): 155–190. doi:10.1007 / s10817-013-9285-6. Yazılım.

Eşitlik teorileri

• Bir ilişkisel ve değişmeli işlem: Pottier, Loic (Şubat 1989), Algoritmalar tamamlanma ve mantıksal genelleme; Pottier, Loic (1989), Genelleme de termes en theorie equationelle - Cas Associatif-CommutatifINRIA Raporu, 1056, INRIA
• Değişmeli teoriler: Baader, Franz (1991). "Birleşme, Zayıf Birleştirme, Üst Sınır, Alt Sınır ve Genelleme Sorunları". Proc. 4. Konf. Yeniden Yazım Teknikleri ve Uygulamaları (RTA) Hakkında. LNCS. 488. Springer. sayfa 86–91.
• Serbest monoidler: Biere, A. (1993), Normalisierung, Unifikation und Antiunifikation in Freien Monoiden (PDF), Univ. Karlsruhe, Almanya
• Düzenli uyum sınıfları: Heinz, Birgit (Aralık 1995), Anti-Unifikation modulo Gleichungstheorie und deren Anwendung zur Lemmagenerierung, GMD Berichte, 261, TU Berlin, ISBN  978-3-486-23873-0; Burghardt, Jochen (2005). "Gramerleri Kullanarak E-Genelleme". Yapay zeka. 165 (1): 1–35. arXiv:1403.8118. doi:10.1016 / j.artint.2005.01.008.
• Sıralı türlerle A-, C-, AC-, ACU-teorileri: Alpuente, Maria; Escobar, Santiago; Espert, Javier; Meseguer, Jose (2014). "Modüler sıralı bir denklem genelleme algoritması" (PDF). Bilgi ve Hesaplama. 235: 98–136. doi:10.1016 / j.ic.2014.01.006. hdl:2142/25871.
• Tamamen idempontent teorileri: Cerna, David; Kutsia, Temur (2019). "Idempotent Anti-Unification". Hesaplamalı Mantıkta ACM İşlemleri. 21 (2). hdl:10.1145/3359060.

Birinci dereceden sıralanmış birleşme önleme

• Taksonomik türler: Frisch, Alan M .; Sayfa, David (1990). "Taksonomik Bilgilerle Genelleme". AAAI: 755–761.; Frisch, Alan M .; Sayfa Jr., C. David (1991). "Kısıtlama Mantığında Atomları Genelleştirme". Proc. Conf. Bilgi Temsili hakkında.; Frisch, A.M .; Sayfa, C.D. (1995). "Örneklemeye Teoriler Oluşturmak". Mellish, C.S. (ed.). Proc. 14 IJCAI. Morgan Kaufmann. sayfa 1210–1216.
• Özellik terimleri: Plaza, E. (1995). "Koşullar Olarak Vakalar: Vakaların Yapılandırılmış Temsiline Bir Özellik Terimi Yaklaşımı". Proc. 1. Uluslararası Vakaya Dayalı Akıl Yürütme Konferansı (ICCBR). LNCS. 1010. Springer. s. 265–276. ISSN  0302-9743.
• Idestam-Almquist, Peter (Haziran 1993). "Yinelemeli Birleşmeyi Önleme Yoluyla Uygulama Altında Genelleştirme". Proc. 10. Konf. Makine Öğreniminde. Morgan Kaufmann. s. 151–158.
• Fischer, Cornelia (Mayıs 1994), PAntUDE - Rafine Genelleştirmeleri İfade Etmek İçin Bir Birleşmeyi Önleme Algoritması, Araştırma Raporu, TM-94-04, DFKI
• Sıralı türlerle A-, C-, AC-, ACU-teorileri: yukarıyı görmek

Nominal birleşme önleme

• Baumgartner, Alexander; Kutsia, Temur; Levy, Jordi; Villaret, Mateu (Haz 2013). Nominal Birleşme Karşıtı. Proc. RTA 2015. Cilt. 36 LIPIcs. Schloss Dagstuhl, 57-73. Yazılım.

Başvurular

• Program analizi: Bulychev, Peter; Minea Marius (2008). "Anti-Birleştirme Kullanarak Yinelenen Kod Algılama". Alıntı dergisi gerektirir | günlük = (Yardım); Bulychev, Peter E .; Kostylev, Egor V .; Zakharov, Vladimir A. (2009). "Anti-Birleşim Algoritmaları ve Program Analizinde Uygulamaları". Alıntı dergisi gerektirir | günlük = (Yardım)
• Kod faktoringi: Cottrell, Rylan (Eyl 2008), Küçük Ölçekli Kaynak Kodunun Yapısal Yazışmalarla Yeniden Kullanımı Yarı Otomatikleştirilmesi (PDF), Univ. Calgary
• İndüksiyon kanıtlama: Heinz, Birgit (1994), Düzenli Türlerin Birleşmesini Önleyerek Lemma Keşfi, Teknik Rapor, 94-21, TU Berlin
• Bilgi Çıkarma: Thomas, Bernd (1999). "Bilgi Çıkarma için T-Sarmalayıcıların Birleşmeyi Önleme Temelli Öğrenmesi" (PDF). AAAI Teknik Raporu. WS-99-11: 15–20.
• Vakaya dayalı muhakeme: Armengol, Eva; Plaza, Enric (2005). "CBR'deki Benzerliği Açıklamak İçin Sembolik Açıklamaları Kullanma" (PDF). Alıntı dergisi gerektirir | günlük = (Yardım)
• Program sentezi: Bir eşitlik teorisine göre terimleri genelleme fikri, onu program sentezinde uygulamak isteyen Manna ve Waldinger'e (1978, 1980) kadar izlenebilir. "Genelleme" bölümünde, (1980 tarihli makalenin 119. sayfasında) tersine çevirmek(l) ve tersine çevirmek(kuyruk(l))<>[baş(l)] elde etmek üzere ters (l ') <> m' . Bu genelleme ancak arka plan denklemi sen<>[]=sen düşünülmektedir.

Zohar Manna; Richard Waldinger (Aralık 1978). Program Sentezine Tümdengelimli Bir Yaklaşım (PDF) (Teknik not). SRI Uluslararası. - 1980 tarihli makalenin ön baskısı

Zohar Manna ve Richard Waldinger (Ocak 1980). "Program Sentezine Tümdengelimli Bir Yaklaşım". Programlama Dilleri ve Sistemlerinde ACM İşlemleri. 2: 90–121. doi:10.1145/357084.357090.

Ağaçların birleşmesi ve dilbilimsel uygulamalar

• Ağaçları ayrıştır Cümleler, dil öğrenimi için maksimum ortak alt ayrıştırma ağaçları türetmek için en az genel genellemeye tabi olabilir. Arama ve metin sınıflandırmada uygulamalar vardır.^[4]
• Ayrıştırma çalılıkları grafik olarak paragraflar için en az genellemeye tabi olabilir.^[5]
• Genelleme işlemi, sözdizimsel (ayrıştırma ağaçları) anlamsal (sembolik ifadeler) düzeye geçiş işlemiyle değişmektedir. İkincisi daha sonra geleneksel anti-birleşmeye tabi olabilir.^[6][7]

Üst düzey birleşme karşıtı

Bu bölüm genişlemeye ihtiyacı var ile: (yukarıdaki gibi). Yardımcı olabilirsiniz ona eklemek. (Haziran 2020)

• Yapı hesabı: Pfenning, Frank (Temmuz 1991). "Yapılar Hesaplamasında Birleşme ve Birleşmeyi Önleme" (PDF). Proc. 6. LICS. Springer. s. 74–85.
• Basitçe yazılmış lambda hesabı (Girdi: eta-uzun beta-normal biçimindeki terimler. Çıktı: yüksek mertebeden örüntüler): Baumgartner, Alexander; Kutsia, Temur; Levy, Jordi; Villaret, Mateu (Haz 2013). Yüksek Dereceli Birleşmeyi Önleme Varyantı. Proc. RTA 2013. Cilt. 21 LIPIcs. Schloss Dagstuhl, 113-127. Yazılım.
• Basitçe yazılmış lambda hesabı (Giriş: eta-uzun beta-normal biçimindeki terimler. Çıktı: Örüntüler dahil basit yazılı lambda hesabının çeşitli parçaları): Cerna, David; Kutsia, Temur (Haziran 2019). "Yüksek Dereceli Genellemeler için Genel Bir Çerçeve" (PDF). 4. Uluslararası Hesaplama ve Tümdengelim için Biçimsel Yapılar Konferansı, FSCD, 24–30 Haziran 2019, Dortmund, Almanya. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. s. 74–85.
• Kısıtlanmış Yüksek Dereceli İkameler: Wagner, Ulrich (Nisan 2002), Kombinatorik Olarak Sınırlandırılmış Yüksek Dereceli Birleşme Karşıtı, TU Berlin; Schmidt, Martin (Eyl 2010), Sezgisel Güdümlü Teori Projeksiyonu için Sınırlandırılmış Yüksek Dereceli Birleşme Karşıtı (PDF), PICS-Raporu, 31-2010, Univ. Osnabrück, Almanya, ISSN  1610-5389

Notlar

Referanslar