Kekemelik eşdeğerliği - Stuttering equivalence

Bu makale çoğu okuyucunun anlayamayacağı kadar teknik olabilir. Lütfen geliştirmeye yardım et -e uzman olmayanlar için anlaşılır hale getirinteknik detayları kaldırmadan. (Temmuz 2012) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

İçinde teorik bilgisayar bilimi, kekemelik denkliği,^[1] olarak yazılmış bir ilişki

Yollar ${ displaystyle pi}$ ve ${ displaystyle pi '}$ kekemelik eşdeğerdir.

${ displaystyle pi sim _ {st} pi '}$,

yolun bölümlenmesi olarak görülebilir ${ displaystyle pi}$ ve ${ displaystyle pi '}$ bloklar halinde, böylece ${ displaystyle k ^ { mathrm {th}}}$ bir yol bloğu etiketlenir (${ displaystyle L ( cdot)}$) içindeki durumlarla aynı ${ displaystyle k ^ { mathrm {th}}}$ diğer yolun bloğu. Karşılık gelen blokların farklı uzunlukları olabilir.

Resmi olarak, bu iki sonsuz yol olarak ifade edilebilir ${ displaystyle pi = s_ {0}, s_ {1}, ldots}$ ve ${ displaystyle pi '= r_ {0}, r_ {1}, ldots}$ kekemelik eşdeğeri olan (${ displaystyle pi sim _ {st} pi '}$) iki sonsuz tam sayı dizisi varsa ${ displaystyle 0 = i_ {0}$ ve ${ displaystyle 0 = j_ {0}$ öyle ki her blok için ${ displaystyle k geq 0}$ tutar ${ displaystyle L (s_ {i_ {k}}) = L (s_ {i_ {k} +1}) = ldots = L (s_ {i_ {k + 1} -1}) = L (r_ {j_ {k}}) = L (r_ {j_ {k} +1}) = ldots = L (r_ {j_ {k + 1} -1})}$.

Kekemelik eşdeğerliği ile aynı şey değildir bisimülasyon, bisimülasyon, içinde bulunan 'eninde sonunda' (veya 'sonunda') işlecinin anlamını yakalayamadığından doğrusal zamansal /hesaplama ağacı mantığı (dallanma süresi mantığı) (modal mantık ). Lafta dallanma bisimülasyonu kullanılmalı.^{[kaynak belirtilmeli ]}

Referanslar