Kritický pár (logika) - Critical pair (logic)

Trojúhelníkový diagram kritického páru získaný ze dvou přepisovacích pravidel s → t (horní řada, vlevo) a l→r (že jo). The substituce σ sjednocuje the dílčí termín s|_str s l. Výsledný překryvný termín sσ[lσ]_str (spodní řádek, prostřední) lze přepsat na termín tσ a sσ[rσ ']_str (spodní řádek, vlevo a vpravo). Poslední dva pojmy tvoří kritický pár. Mohou být nakonec přepsány na běžný výraz, pokud je sada pravidel přepsání soutok.

v matematická logika, a kritický pár vzniká v systémy přepisování termínů kde se pravidla přepisování překrývají a poskytují dva různé výrazy. Více dopodrobna, (t₁, t₂) je kritický pár, pokud existuje výraz t pro které dvě různé aplikace pravidla přepsání (buď stejné pravidlo platí odlišně, nebo dvě různá pravidla) poskytují podmínky t₁ a t₂.

Například v pojmu přepisovací systém s pravidly

F(G(X,y),z)	→ G(X,z)
G(X,y)	→ X,

jediný kritický pár je ⟨G(X,z), F(X,z)⟩. Oba tyto pojmy lze odvodit z tohoto pojmu F(G(X,y),z) použitím pravidla jediného přepsání.

Jako další příklad zvažte termín přepisovací systém s jediným pravidlem

F(X,y)

→ X.

Aplikováním tohoto pravidla na tento výraz dvěma různými způsoby F(F(X,X),X), vidíme, že (F(X,X), F(X,X)) je (triviální) kritický pár.

Když mohou obě strany kritického páru snížit ke stejnému termínu se nazývá kritická dvojice konvergentní. Pokud je jedna strana kritického páru identická s druhou, volá se kritický pár triviální.

Pokud termín přepisovací systém není soutok se nemusí kritický pár sbíhat, takže kritické páry jsou potenciálními zdroji, u nichž dojde k selhání soutoku. Ve skutečnosti lemma kritického páru uvádí, že systém přepisování termínů je slabě (také místně) splývající pokud jsou všechny kritické páry konvergentní. Chcete-li tedy zjistit, zda je systém přepisování pojmů slabě splývající, stačí otestovat všechny kritické páry a zjistit, zda jsou konvergentní. To umožňuje algoritmicky zjistit, zda je systém přepisování termínů slabě splývavý nebo ne, vzhledem k tomu, že lze algoritmicky zkontrolovat, zda se dva termíny sbližují.

Ze slabého soutoku jasně vyplývají konvergentní kritické páry: pokud existuje kritický pár ⟨A, bVzniká tedy ises A a b mají společnou redukci a tak je kritická dvojice konvergentní.

Viz také

• Dokončení Knuth – Bendix, algoritmus založený na kritických párech pro výpočet a soutok a ukončení systém přepisování termínů ekvivalentní danému

externí odkazy

• Weisstein, Eric W. „Kritický pár“. MathWorld.

Reference

• Franz Baader a Tobias Nipkow, Přepisování termínů a tak dále, Cambridge University Press, 1998 (rezervovat webový odkaz)
• Terese, Systémy přepisování termínů, Cambridge Tracts in Theoretical Computer Science, 2003. (rezervovat webový odkaz)