Překrytí (přepis termínu) - Overlap (term rewriting)

v matematika, počítačová věda a logika, překrytí, jako vlastnost pravidel snižování v systém přepisování termínů, popisuje situaci, kdy řada různých pravidel redukce specifikuje potenciálně protichůdné způsoby redukce redukovatelného výrazu, známého také jako redex, v období.^[1]

Přesněji řečeno, pokud řada různých pravidel redukce sdílí funkční symboly na levé straně, může dojít k překrytí. Často nepovažujeme banální překrývání s redexem a sebou samým.

Příklady

Zvažte systém přepisování termínů definovaný následujícími pravidly redukce:

{displaystyle ho _ {1}: f (g (x), y) ightarrow y}

{displaystyle ho _ {2}: g (x) ightarrow f (x, x)}

Termín ${displaystyle f (g (x), y)}$ lze snížit pomocí ρ₁ poddat se $y$ , ale lze jej také snížit pomocí ρ₂ poddat se ${displaystyle f (f (x, x), y).}$ . Všimněte si, jak redex ${displaystyle g (x)}$ je obsažen v redexu ${displaystyle f (g (x), y)}$ . Výsledek redukce různých redexů je popsán v tzv. A kritický pár; kritická dvojice vyplývající z tohoto termínu přepisovací systém je ${displaystyle (f (f (x, x), y), y)}$ .

Může dojít k překrývání s méně než dvěma pravidly redukce.

Vezměme si pojem systém přepisování definovaný následujícím pravidlem redukce:

{displaystyle ho _ {1}: g (g (x)) ightarrow x}

Termín ${displaystyle g (g (g (x)))}$ má překrývající se redexy, které lze použít buď na nejvnitřnější výskyt, nebo na nejvzdálenější výskyt ${displaystyle g (g (x))}$ období.

Reference

^ Marc Bezem; Jan Willem Klop; Roel de Vrijer (2003). Systémy přepisování termínů. Cambridge Tracts v teoretické informatice. Cambridge, Velká Británie: Cambridge University Press. str. 48. ISBN 0-521-39115-6.

Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Marc Bezem; Jan Willem Klop; Roel de Vrijer (2003). Systémy přepisování termínů. Cambridge Tracts v teoretické informatice. Cambridge, Velká Británie: Cambridge University Press. str. 48. ISBN 0-521-39115-6.

[1]