Koktání ekvivalence - Stuttering equivalence

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Červenec 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teoretická informatika, koktavost,^[1] vztah psaný jako

Cesty ${ displaystyle pi}$ a ${ displaystyle pi '}$ jsou koktavé ekvivalenty.

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

lze chápat jako rozdělení cesty ${ displaystyle pi}$ a ${ displaystyle pi '}$ do bloků, takže se uvádí v ${ displaystyle k ^ { mathrm {th}}}$ blok jedné cesty jsou označeny (${ displaystyle L ( cdot)}$) stejné jako státy v ${ displaystyle k ^ { mathrm {th}}}$ blok druhé cesty. Odpovídající bloky mohou mít různé délky.

Formálně to lze vyjádřit jako dvě nekonečné cesty ${ displaystyle pi = s_ {0}, s_ {1}, ldots}$ a ${ displaystyle pi '= r_ {0}, r_ {1}, ldots}$ které jsou koktavé ekvivalentní (${ displaystyle pi sim _ {st} pi '}$) pokud existují dvě nekonečné sekvence celých čísel ${ displaystyle 0 = i_ {0}$ a ${ displaystyle 0 = j_ {0}$ tak, že pro každý blok ${ displaystyle k geq 0}$ drží ${ 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})}$.

Rovnováha koktání není stejná jako bisimulace, protože bisimulace nemůže zachytit sémantiku operátoru „nakonec“ (nebo „konečně“) nalezeného v lineární časové /logika výpočetního stromu (logika větvícího času) (modální logika ). Tzv rozvětvená bisimulace musí být použito.^{[Citace je zapotřebí ]}

Reference