Yol sıralaması (terim yeniden yazma) - Path ordering (term rewriting)

İçinde teorik bilgisayar bilimi özellikle terim yeniden yazma, bir yol sıralaması bir sağlam temelli kesin toplam sipariş (>) tüm sette şartlar öyle ki

f(...) > g(s₁,...,s_n) Eğer f ^.> g ve f(...) > s_ben için ben=1,...,n,

nerede (^.>) kullanıcı tarafından verilir toplam öncelik sırası hepsinin setinde fonksiyon sembolleri.

Sezgisel olarak, bir terim f(...) herhangi bir terimden daha büyüktür g[...) şartlardan inşa edilmiştir s_ben daha küçük f[...) daha düşük öncelikli kök sembolü kullanarak gÖzellikle, yapısal indüksiyon, bir terim f[...) yalnızca şundan küçük sembolleri içeren herhangi bir terimden daha büyüktür f.

Yol sıralaması genellikle şu şekilde kullanılır: indirim siparişi terim yeniden yazmada, özellikle Knuth – Bendix tamamlama algoritması Örnek olarak, "yeniden yazma sistemi" terimiçarpmak "matematiksel ifadeler bir kural içerebilir x*(y+z) → (x*y) + (x*z). Kanıtlamak için sonlandırma, bir indirim siparişi (>) terim ile ilgili bulunmalıdır x*(y+z) terimden daha büyüktür (x*y)+(x*z). Önceki terim, ikincisinden hem daha az işlev sembolü hem de daha az değişken içerdiğinden, bu önemsiz değildir. Ancak, önceliği ayarlama (*) ^.> (+), bir yol sıralaması kullanılabilir, çünkü her ikisi de x*(y+z) > x*y ve x*(y+z) > x*z elde etmesi kolaydır.

İki terim verildiğinde s ve t, bir kök simgesiyle f ve gsırasıyla, ilişkilerine karar vermek için önce kök sembolleri karşılaştırılır.

• Eğer f <^. g, sonra s hakim olabilir t sadece biri s 'alt terimleri yapar.
• Eğer f ^.> g, sonra s hakim t Eğer s her birine hakim t 's alt terimleri.
• Eğer f = g, sonra hemen alt terimler nın-nin s ve t özyinelemeli olarak karşılaştırılması gerekir. Belirli yönteme bağlı olarak, farklı yol sıralaması varyasyonları mevcuttur.^[1][2]

İkinci varyasyonlar şunları içerir:

• çok kümeli yol sıralaması (mpo), başlangıçta yinelemeli yol sıralaması (rpo)^[3]
• sözlükbilimsel yol sıralaması (lpo)^[4]
• mpo ve lpo'nun bir kombinasyonu, adı verilen yinelemeli yol sıralaması Dershowitz, Jouannaud (1990)^[5][6][7]

Dershowitz, Okada (1988) daha fazla varyant listeliyor ve bunları Ackermann sistemi sıra sayıları.

Biçimsel tanımlar

çok kümeli yol sıralaması (>) şu şekilde tanımlanabilir:^[8]

nerede

• (≥), dönüşlü kapanma mpo (>),
• { s₁,...,s_m } gösterir çoklu set nın-nin sİçin benzer alt terimleri t, ve
• (>>), (>) 'nin çoklu kümeli uzantısını belirtir. { s₁,...,s_m } >> { t₁,...,t_n } Eğer { t₁,...,t_n } şuradan elde edilebilir { s₁,...,s_m }
  • en az bir öğeyi silerek veya
  • bir öğeyi kesinlikle daha küçük (mpo w.r.t.) öğelerden oluşan bir çoklu kümeyle değiştirerek.^[9]

Daha genel olarak bir sipariş işlevsel bir işlev Ö bir siparişi başka bir siparişe eşlemek ve aşağıdaki özellikleri yerine getirmek:^[10]

• Eğer (>) ise geçişli Öyleyse öyle Ö(>).
• Eğer (>) ise yansımasız Öyleyse öyle Ö(>).
• Eğer s > t, sonra f(...,s,...) Ö(>) f(...,t,...).
• Ö dır-dir sürekli ilişkilerde, yani eğer R₀, R₁, R₂, R₃, ... sonsuz bir ilişkiler dizisidir, o zaman Ö(∪^∞
  _ben=0 R_ben) = ∪^∞
  _ben=0 Ö(R_ben).

Çoklu kümeli uzantı, yukarıdaki (>) ile (>>) arasındaki eşleme işlevsel bir sipariş örneğidir: (>>) =Ö(>). İşlevsel olan başka bir düzen, alfabetik sırayla uzantı, yol açar sözlükbilimsel yol sıralaması.

Referanslar