SW wykład 9 - Slajd12

<<powrót do strony wykładu

Dziedziny podstawowe Suma i produkt Suma spłaszczona i produkt spłaszczony Przestrzeń funkcji ciągłych Izomorfizm dziedzin Konstruowanie funkcji ciągłych Złożenie funkcji i indeksowanie Inne konstrukcje Operator punktu stałego Równania stałopunktowe Równania dziedzinowe Rekurencyjne równania dziedzinowe Rekurencyjne równania dziedzinowe Problemy Dziedziny refleksywne Rozwiązanie naiwne dziedziny Scotta

Spójrzmy na równanie dziedzinowe definiujące nieskończone potoki elementów z (płaskiego) ustalonego zbioru, jak w ramce na górze slajdu.

Podobnie jak dla równań stałopunktowych definiujących elementy w zbiorze łańcuchowo zupełnym, iterujemy operator zadany prawą stroną tego równania począwszy od "najmniejszego", "pustego" (czyli zawierającego tylko denko) zbioru łańcuchowo zupełnego --- o jego jedynym elemencie można myśleć jako o zupełnie "nieokreślonym" potoku. W pierwszej iteracji, budujemy produkt zbioru elementów z dotychczas skonstruowaną aproksymacją dla definiowanego zbioru: otrzymujemy, poza "potokiem nieokreślonym", także pary, złożone z elementów i "potoku nieokreślonego". Kolejna iteracja dokłada do tego pary, gdzie drugi element może być parą otrzymaną w poprzedniej iteracji. I tak dalej.

Aby ułatwić dalszą analizę, zmienimy nieco notację. Ale jeszcze wcześniej, zwróćmy uwagę, że w powyższych iteracjach powstające pary mogą mieć jako swój pierwszy element także "denko" (pochodzące z płaskiego zbioru elementów). Aby uniknąć takich nieokreślonych elementów w naszych potokach, zmieńmy nieco rozważane równanie, gdzie produkt zastąpimy produktem "spłaszczonym z lewej strony". Formalnie jest on definiowany jako produkt spłaszczony pierwszego argumentu z podniesionym o nowy element najmniejszy drugim argumentem (patrz slajd 9, wykład 6).