Newmanovo lemma - Newmans lemma - Wikipedia

v matematika, v teorii přepis systémy, Newman's lemma, také běžně nazývaný diamantové lema, uvádí, že a ukončení (nebo silně normalizující) abstraktní přepisovací systém (ARS), tj. Ten, ve kterém neexistují žádné nekonečné redukční sekvence, je soutok Pokud to je místně splývající. Ve skutečnosti končící ARS splývá přesně kdy je místně splývající.[1]

Ekvivalentně pro každého binární relace bez klesajících nekonečných řetězců a uspokojení slabé verze diamantové vlastnosti existuje jedinečný minimální prvek v každé připojená součást vztahu považovaného za a graf.

Dnes je to považováno za čistě kombinatorický výsledek založený na opodstatněnost z důvodu prokázání Gérard Huet v roce 1980.[2] Newmanův původní důkaz byl podstatně složitější.[3]

Diamantové lema

Důkaz (přímé a vlnovky označující → a ∗→, v uvedeném pořadí):
Dáno t1 ∗←t∗→t2, proveďte indukci délky derivace. Získat t′ z místního soutoku a t′′ z indukční hypotézy; podobné pro t′′′.

Newmanovo lemma lze obecně považovat za a kombinační výsledek o binárních vztazích → na množině A (napsáno dozadu, takže A → b znamená, že b je níže A) s následujícími dvěma vlastnostmi:

  • → je a opodstatněný vztah: každá neprázdná podmnožina X z A má minimální prvek (prvek A z X takhle A → b pro č b v X). Ekvivalentně neexistuje žádný nekonečný řetězec A0 → A1 → A2 → A3 → .... V terminologii přepisovacích systémů → končí.
  • Každá krytina je ohraničena níže. To znamená, že pokud prvek A v A pokrývá prvky b a C v A V tom smyslu, že A → b a A → C, pak existuje prvek d v A takhle b ∗→ d a C ∗→ d, kde ∗→ označuje reflexní přechodné uzavření z →. V terminologii přepisovacích systémů je → lokálně splývající.

Pokud platí výše uvedené dvě podmínky, pak lemma říká, že → je splývající: kdykoli A ∗→ b a A ∗→ C, existuje prvek d takhle b ∗→ d a C ∗→ d. Z pohledu ukončení → to znamená, že každá připojená součást → jako graf obsahuje jedinečný minimální prvek A, navíc b ∗→ A pro každý prvek b součásti.[4]

Poznámky

  1. ^ Franz Baader, Tobias Nipkow, (1998) Přepisování termínů a tak dále, Cambridge University Press ISBN  0-521-77920-0
  2. ^ Gérard Huet „Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems“, Deník ACM (JACM ), Říjen 1980, svazek 27, Vydání 4, str. 797 - 821.
  3. ^ Harrison, str. 260, Paterson (1990), str. 354.
  4. ^ Paul M. Cohn, (1980) Univerzální algebra, D. Reidel Publishing, ISBN  90-277-1254-9 (Viz str. 25–26)

Reference

Učebnice

  • Systémy přepisování termínů, Terese, Cambridge Tracts in Theoretical Computer Science, 2003. (rezervovat webový odkaz)
  • Přepisování termínů a tak dále, Franz Baader a Tobias Nipkow, Cambridge University Press, 1998 (rezervovat webový odkaz)
  • John Harrison, Příručka praktické logiky a automatického uvažování, Cambridge University Press, 2009, ISBN  978-0-521-89957-4, kapitola 4 „Rovnost“.

externí odkazy