Filtrelenmiş-patlayan özyinelemeli geçiş ağı - Filtered-popping recursive transition network - Wikipedia

Bir filtrelenmiş, özyinelemeli geçiş ağı (FPRTN),^[1] ya da sadece filtrelenen ağ (FPN), bir yinelemeli geçiş ağı (RTN )^[2] bir durum haritasından geri dönüldüğünde anahtarlara altyordam jump, alıcı ve dönüş durumlarının aynı anahtara eşlenmesini gerektirir. RTN'ler vardır sonlu durum makineleri şu şekilde görülebilir sonlu durumlu otomata ile genişletilmiş yığın dönüş durumlarının oranı; geçişleri tüketmenin yanı sıra ve ${ displaystyle varepsilon}$- geçişler, RTN'ler çağrı geçişlerini tanımlayabilir. Bu geçişler bir altyordam geçişin hedef durumunu yığına iterek ve makineyi çağrılan duruma getirerek atlayın. Bir kabul durumuna her ulaşıldığında, yığının boş olmaması koşuluyla yığının en üstündeki dönüş durumu dışarı çıkar ve makine bu duruma getirilir.

Bu makale boyunca, filtrelenmiş-patlayan özyinelemeli geçiş ağlarına şu şekilde değineceğiz: FPN'ler, bu kısaltma belirsiz olsa da (örneğin: tüylü Petri ağları ). Filtrelenen ağlar ve FPRTN'ler kesin alternatiflerdir.

Resmi tanımlama

Bir FPN bir yapıdır ${ displaystyle (Q, K, Sigma, delta, kappa, Q_ {I}, F)}$ nerede

• ${ displaystyle Q}$ sonlu bir durum kümesidir,
• ${ displaystyle K}$ sınırlı bir anahtar dizisidir,
• ${ displaystyle Sigma}$ sonlu bir giriş alfabesidir,
• ${ displaystyle delta: Q times ( Sigma cup { varepsilon } cup Q) ile Q}$ kısmi bir geçiş işlevidir, ${ displaystyle varepsilon}$ boş sembol olmak,
• ${ displaystyle kappa: Q ila K}$ anahtarların durumları haritasıdır,
• ${ displaystyle Q_ {I} subseteq Q}$ başlangıç ​​durumları kümesidir ve
• ${ displaystyle F subseteq Q}$ kabul durumları kümesidir.

Geçişler

Geçişler, FPN'yi bir kaynak durumdan getirme olasılığını temsil eder ${ displaystyle q_ {s}}$ hedef duruma ${ displaystyle q_ {t}}$ muhtemelen ek bir eylem gerçekleştirerek. Bu eyleme bağlı olarak, aşağıdaki türlerini ayırt ediyoruz açıkçatanımlı geçişler:

• ${ displaystyle varepsilon}$geçişler formun geçişleridir ${ displaystyle delta (q_ {s}, varepsilon) ile q_ {t}}$ ve hiçbir ek işlem yapmayın,
• tüketen geçişler formun geçişleridir ${ displaystyle delta (q_ {s}, sigma) ile q_ {t}}$ ve bir giriş sembolü tüketin ${ displaystyle sigma}$, ve
• çağrı geçişleri formun geçişleridir ${ displaystyle delta (q_ {s}, q_ {c}) ile q_ {t}}$ ve gerçekleştir altyordam aranan duruma geç ${ displaystyle q_ {c}}$ ulaşmadan önce ${ displaystyle q_ {t}}$.

Çağrı geçişlerinin davranışı, iki tür dolaylı olaraktanımlı geçişler:

• her çağrı geçişi için ${ displaystyle delta (q_ {s}, q_ {c}) ile q_ {t}}$ FPN örtük olarak bir itme geçişi bu makineyi getiriyor ${ displaystyle q_ {s}}$ -e ${ displaystyle q_ {c}}$ iterek ${ displaystyle q_ {t}}$ üzerine yığın, ve
• her bir durum çifti için ${ displaystyle (q_ {f}, q_ {r}) in F times Q}$ FPN örtük olarak bir pop geçişi bu makineyi getiriyor ${ displaystyle q_ {f}}$ -e ${ displaystyle q_ {r}}$ patlayarak ${ displaystyle q_ {r}}$ yığından iff ${ displaystyle q_ {r}}$ yığının en üstündeki durum ve ${ displaystyle kappa (q_ {f}) = kappa (q_ {r})}$.

Push geçişleri başlatılır altyordam sıçramalar ve pop geçişleri eşdeğerdir dönüş ifadeleri.

Amaç

A (Doğal lisan ) metin, meta bilgilerle zenginleştirilebilir. Çıkışlı RTN; örneğin, bir RTN yerleştirme XML etiketleri dönüştürmek için kullanılabilir düz metin yapılandırılmış bir XML belgesine. Çıktıyı temsil eden bir RTN Doğal lisan dilbilgisi her metin cümlesinin sözdizimsel yapısını sınırlar ve ekler (bkz. ayrıştırma ). Çıktıya sahip diğer RTN'ler, ilgili bilgileri içeren metin bölümlerini basitçe işaretleyebilir (bkz. bilgi çıkarma ). Çıktıyı temsil eden bir RTN uygulaması belirsiz gramer girdinin olası çevirileri veya yorumlarıyla sonuçlanır. Bu kümenin hesaplanması üstel bir en kötü durum maliyeti hatta bir Earley ayrıştırıcı çıkışlı RTN'ler için,^[3] çeviri sayısının katlanarak arttığı durumlar nedeniyle w.r.t. giriş uzunluğu; örneğin, bir Doğal lisan cümle üssel olarak artar. çözülmemişlerin sayısı tamlamalar ekler:^[4][5]

• cümle içinde kız maymunu teleskopla gördüKızın teleskopu mu kullandığı yoksa maymunun mu tuttuğu bilinmemektedir (2¹ yorumlar),
• cümle içinde Kız bahçede teleskopla maymunu gördümaymunun bahçede mi yoksa bahçede mi olduğu da bilinmemektedir (2² yorumlar),
• cümle içinde Kız bahçede ağacın altında teleskopla maymunu gördümaymunun ağacın altında mı olduğu yoksa eylemin ağacın altında mı olduğu da bilinmemektedir (2³ yorumlar),
• vb.

FPN'ler, Earley benzeri bir ayrıştırıcı aracılığıyla kübik zamanda hesaplanmasına izin vererek, bu çeviri kümesinin kompakt bir temsili olarak hizmet eder.^[1] FPN durumları, yürütme durumlarına karşılık gelir (bkz. talimat adımları ) için bir Earley ayrıştırıcısı RTN'ler olmadan çıktı ve FPN geçişleri, giriş simgelerinin olası çevirilerine karşılık gelir. ${ displaystyle kappa}$ Ortaya çıkan FPN'nin haritası, gösterilen çıkış segmentleri ile tanınan giriş segmentleri arasındaki yazışmayı verir: tanınan bir giriş dizisi verildiğinde ${ displaystyle sigma _ {1} ldots sigma _ {l}}$ ve bir FPN yolu ${ displaystyle p}$ bir eyalette başlamak ${ displaystyle q}$ ve bir durumda bitiyor ${ displaystyle q ^ { prime}}$, ${ displaystyle p}$ girdi segmentinin olası bir çevirisini temsil eder ${ displaystyle sigma _ { kappa (q) +1} ldots sigma _ { kappa (q ^ { prime})}}$. FPN yollarının çevirilerini temsil etmesini önlemek için filtrelenmiş popping özelliği gereklidir. bağlantı kesildi veya örtüşen giriş segmentleri: bir FPN çağrısı, aranan durumdan bir alıcı duruma kadar birkaç çeviri yolu içerebilir, burada karşılık gelen giriş segmentleri aynı başlangıç ​​noktasını paylaşır, ancak mutlaka aynı uzunluğa sahip değildir. Yalnızca aramayı bitiren alıcı durumundan aynı giriş noktasına karşılık gelen dönüş durumları geçerli dönüş durumları.

Referanslar