Soutok (přepis abstraktu) - Confluence (abstract rewriting)
 | Bylo navrženo, aby tento článek byl sloučeny s Konvergence (logika). (Diskutujte) Navrhováno od září 2020. |
V počítačové vědě soutok je majetkem přepis systémy, popisující, které výrazy v takovém systému lze přepsat více než jedním způsobem, aby přinesly stejný výsledek. Tento článek popisuje vlastnosti v nejvíce abstraktním prostředí abstraktní přepisovací systém.
Motivující příklady
Obvyklá pravidla elementární aritmetiky tvoří abstraktní přepisovací systém. Například výraz (11 + 9) × (2 + 4) lze vyhodnotit počínaje levou nebo pravou závorkou; v obou případech je však stejný výsledek To naznačuje, že aritmetický přepisovací systém je konfluentní.
Druhý, abstraktnější příklad je získán z následujícího důkazu každého z nich skupina prvek rovnající se inverzní jeho inverzní:[1]
| A1 | 1 ⋅ A | = A |
| A2 | A−1 ⋅ A | = 1 |
| A3 | (A ⋅ b) ⋅ C | = A ⋅ (b ⋅ C) |
| A−1 ⋅ (A ⋅ b) | ||
| = | (A−1 ⋅ A) ⋅ b | podle A3 (r) |
| = | 1 ⋅ b | podle A2 |
| = | b | podle A1 |
| (A−1)−1 ⋅ 1 | ||
| = | (A−1)−1 ⋅ (A−1 ⋅ A) | podle A2 (r) |
| = | A | podle R4 |
| (A−1)−1 ⋅ b | ||
| = | (A−1)−1 ⋅ (A−1 ⋅ (A ⋅ b)) | podle R4 (r) |
| = | A ⋅ b | podle R4 |
| A ⋅ 1 | ||
| = | (A−1)−1 ⋅ 1 | podle R10 (r) |
| = | A | podle R6 |
| (A−1)−1 | ||
| = | (A−1)−1 ⋅ 1 | podle R11 (r) |
| = | A | podle R6 |
Tento důkaz vychází z daných skupinových axiomů A1-A3 a zavádí pět výroků R4, R6, R10, R11 a R12, přičemž každý z nich používá některé dřívější a R12 je hlavní teorém. Některé důkazy vyžadují nenápadné, ne-li kreativní kroky, jako je použití axiomu A2 obráceně, čímž se přepíše „1“ na „A−1 ⋅ a "v prvním kroku důkazu R6. Jedna z historických motivací k rozvoji teorie přepisování termínů bylo vyhnout se potřebě takových kroků, které těžko najde nezkušený člověk, natož počítačový program.
Pokud systém přepisování termínů je soutok a ukončení, existuje přímá metoda k prokázání rovnosti mezi dvěma výrazy (a.k.a. podmínky ) s a t:Začínání s s, použít rovnosti[poznámka 1] zleva doprava tak dlouho, jak je to možné, případně získání termínu s 'Získat z t termín t ’ podobným způsobem. Pokud oba pojmy s ' a t ’ tedy doslova souhlasím s a t jsou (nepřekvapivě) prokázány rovnocenné. Ještě důležitější je, pokud nesouhlasí, s a t nemůže se rovnat. To znamená, že jakékoli dva pojmy s a t kterou lze prokázat jako rovnocennou, lze tak učinit touto metodou.
Úspěch této metody nezávisí na určitém sofistikovaném pořadí, ve kterém se použijí pravidla přepsání, jako soutok zajišťuje, že jakákoli posloupnost aplikací pravidel nakonec povede ke stejnému výsledku (zatímco ukončení vlastnost zajišťuje, že jakákoli sekvence nakonec vůbec skončí).[2] Pokud tedy pro nějakou teorii rovnic lze poskytnout systém přepisování souhrnných a ukončovacích termínů,[poznámka 2] k prokázání pojmu rovnost není vyžadován žádný nádech kreativity; tento úkol se tak stane přístupným pro počítačové programy. Moderní přístupy řeší obecněji abstraktní přepisovací systémy spíše než období přepisovací systémy; druhé jsou zvláštním případem prvního.
Obecný případ a teorie
Přepisovací systém lze vyjádřit jako a řízený graf ve kterém uzly představují výrazy a hrany představují přepsání. Například pokud je výraz A lze přepsat do b, pak to říkáme b je redukovat z A (alternativně, A snižuje na bnebo A je expanze z b). Toto je reprezentováno pomocí šipkové notace; A → b naznačuje to A snižuje na b. Intuitivně to znamená, že odpovídající graf má směrovanou hranu z A na b.
Pokud existuje cesta mezi dvěma uzly grafu C a d, pak tvoří a redukční sekvence. Například, pokud C → C’ → C’’ → ... → d’ → d, pak můžeme psát C d, což naznačuje existenci redukční sekvence z C na d. Formálně, je reflexně-tranzitivní uzávěr z →. Na příkladu z předchozího odstavce máme (11 + 9) × (2 + 4) → 20 × (2 + 4) a 20 × (2 + 4) → 20 × 6, takže (11 + 9) × ( 2 + 4) 20×6.
S tímto zjištěním lze soutok definovat následovně. A ∈ S je považován za splývající, pokud pro všechny páry b, C ∈ S takhle A b a A C, existuje a d ∈ S s b d a C d. Pokud každý A ∈ S je splývající, říkáme, že → je splývající nebo má Vlastnost Church-Rosser. Tato vlastnost se také někdy nazývá diamantový majetek, podle tvaru diagramu zobrazeného vpravo. Někteří autoři si tento termín vyhrazují diamantový majetek pro variantu diagramu s jedinou redukcí všude; to znamená kdykoli A → b a A → C, musí existovat a d takhle b → d a C → d. Varianta s jednou redukcí je přísně silnější než varianta s více redukcemi.
Místní soutok
Prvek A ∈ S se říká, že je místně (nebo slabě) splývající, pokud pro všechny b, C ∈ S s A → b a A → C tady existuje d ∈ S s b d a C d. Pokud každý A ∈ S je místně splývající, pak → se nazývá místně (nebo slabě) splývající nebo má slabý majetek Church-Rosser. To se liší od soutoku v tom b a C musí být sníženo z A v jednom kroku. Analogicky s tím je soutok někdy označován jako globální soutok.
Vztah , zavedený jako zápis pro redukční sekvence, lze považovat za systém přepisování sám o sobě, jehož vztah je reflexně-tranzitivní uzávěr z →. Protože sekvence redukčních sekvencí je opět redukční sekvencí (nebo ekvivalentně od vytvoření reflexivně-tranzitivního uzávěru je idempotentní ), = . Z toho vyplývá, že → je splývající tehdy a jen tehdy je místně splývající.
Systém přepisování může být místně konfluentní, aniž by byl (globálně) konfluentní. Příklady jsou zobrazeny na obrázcích 3 a 4. Avšak Newmanovo lemma uvádí, že pokud lokálně splývající přepisovací systém nemá žádné nekonečné redukční sekvence (v takovém případě se říká, že ukončení nebo silně normalizující), pak je globálně splývající.
Polokonfluence
Definice lokálního soutoku se liší od definice globálního soutoku v tom, že jsou brány v úvahu pouze prvky dosažené z daného prvku v jediném kroku přepisování. Když vezmeme v úvahu jeden prvek dosažený v jednom kroku a další prvek dosažený libovolnou posloupností, dospějeme k mezilehlému konceptu polokonfluence: A ∈ S se říká, že je polokonfliktní, pokud pro všechny b, C ∈ S s A → b a A C tady existuje d ∈ S s b d a C d; pokud každý A ∈ S je semi-confluent, říkáme, že → je semi-confluent.
Polokonfluentní prvek nemusí být konfluentní, ale semi-konfluentní přepisovací systém je nutně splývající a konfluentní systém je triviálně semi-konfluentní.
Silný soutok
Silná soutok je další variace na místní soutok, která nám umožňuje dospět k závěru, že systém přepisování je globálně splývající. Prvek A ∈ S se říká, že je silně konfluentní, pokud pro všechny b, C ∈ S s A → b a A → C tady existuje d ∈ S s b d a buď C → d nebo C = d; pokud každý A ∈ S je silně splývající, říkáme, že → je silně splývající.
Soutokový prvek nemusí být silně splývající, ale silně splývající systém přepisování je nutně splývající.
Příklady konfluentních systémů
- Redukce polynomů modulo ideálem je konfluentní systém přepisování za předpokladu, že jeden pracuje s a Gröbnerův základ.
- Matsumotova věta vyplývá ze soutoku opletení vztahů.
- β-redukce λ-termínů splývá s Church-Rosserova věta.
Viz také
Poznámky
- ^ pak volal přepsat pravidla zdůraznit jejich orientaci zleva doprava
- ^ The Algoritmus dokončení Knuth – Bendix lze použít k výpočtu takového systému z dané množiny rovnic. Takový systém např. pro skupiny tady, jehož návrhy jsou trvale očíslovány. Jeho použitím je prokázán např. R6 spočívá v aplikaci R11 a R12 v libovolném pořadí na (A−1)−1To1 získat A;; žádná další pravidla nejsou použitelná.
Reference
- Systémy přepisování termínů, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.
- Přepisování termínů a tak dále, Franz Baader a Tobias Nipkow, Cambridge University Press, 1998
- ^ K. H. Bläsius a H.-J. Bürckert, ed. (1992). Deduktionsssysteme. Oldenbourg. str. 291.; zde: str.134; názvy axiomů a výroků navazují na původní text
- ^ Nový druh vědy [1]
- ^ A b N. Dershowitz a J.-P. Jouannaud (1990). "Přepsat systémy". V Jan van Leeuwen (ed.). Formální modely a sémantika. Příručka teoretické informatiky. B. Elsevier. 243–320. ISBN 0-444-88074-7. Zde: str.268, obr. 2a + b.
