Revision 114516858 of "Bereichstheorie" on dewiki

Die '''Bereichstheorie''' ist ein Zweig der Mathematik, der spezielle Arten von [[Halbordnung|Halbordnungen]],  gemeinhin als Domänen bekannt, studiert. Sie kann als ein Teil der Reihenfolgetheorie betrachtet werden. Die Bereichstheorie beinhaltet  wichtige Anwendungen in der Informatik, die in der Funktionensemantik [[Denotationelle Semantik|(denotationellen Semantik)]] insbesondere für funktionale Programmiersprachen, verwendet werden.<ref>[//www.cs.nott.ac.uk/~gmh/domains.html Introduction to Domain Theory School of Computer Science, University of Nottingham] - abgerufen am 02.Februar 2013</ref>

Sie formalisiert die intuitive Vorstellungen von Annäherung und Konvergenz in einer sehr allgemeinen Weise und unterhält enge Beziehungen zur [[Topologie]]. Ein alternativ wichtiger Ansatz zur Funktionensemantik sind die [[Metrischer Raum|metrischen Räume]].

== Motivation und Formulierung ==
Die primäre Motivation für das Studium der Domänen, die durch [[Dana Scott]] in den späten 1960er Jahren initiiert wurde, war die Suche nach der Funktionensemantik des [[Lambda-Kalkül|Lambda-Kalküls]]. Der Lambda-Kalkül ist eine formale Sprache zur Untersuchung von Funktionen. Diese formale Sprache beschreibt Funktionsdefinitionen, das definieren formaler Parameter sowie das Auswerten und Einsetzen aktueller Parameter. In einer rein syntaktischen Weise kann man von einfachen Funktionen auf Funktionen die andere Funktionen übernehmen und ihre Eingabeargumente schließen. Mit syntaktischen Transformationen aus diesem Formalismus, erhält man sogenannte ''Fixpunktkombinatoren'' (der bekannteste ist der ''Y-Kombinator'').
 
Um eine solche Funktionensemantik zu formulieren, könnte man zunächst versuchen, ein Modell für den Lambda-Kalkül, in dem eine echte (gesamte) Funktion mit jedem Lambda-Term assoziiert ist, zu konstruieren. Ein solches Modell würde eine rein syntaktische Verbindung zwischen dem Lambda Kalkül und dem Kalkül als Darstellungsmittel  für Manipulation konkreter mathematischer Funktionen formalisieren. Der kombinatorische Kalkül ist ein solches Modell. Jedoch sind die Elemente des kombinatorischen Kalküls Funktionen aus Funktionen zu Funktionen. Sie können also nicht wirkliche Funktionen sein, sondern lediglich nur Teilfunktionen.

== Berechnung und Modellierung ==
Die Berechnung zur Lösung dieser Schwierigkeit durch [[Formalisierung]] einer Vorstellung von "teilweisen" oder "unvollständigen" Informationen kommt zu einem Ergebnis, das unter folgender Berücksichtigung modelliert wird: 

Für jede Domäne einer Berechnung (zb. natürliche Zahlen), wird ein zusätzliches Element, das eine undefinierte Ausgabe darstellt herangezogen. Die Folge ist das Ergebnis einer Berechnung, die niemals endet. Außerdem wird der Bereich der Berechnung mit einer [[Ordnungsrelation]] versehen, wobei das "undefiniert Ergebnis" das  kleinste Element darstellt. 
Um den wichtigen Schritt eins Modells für den Lambda Kalkül zu finden, ist es notwendig, die Funktionen einer solchen Halbordnung mit garantierten Mindestfixpunkten zu berücksichtigen. Die Menge dieser Funktionen, zusammen mit einer geeigneten Reihenfolge, ist wiederum eine "Domäne" im Sinne der Bereichstheorie. 

Durch die Beschränkung auf eine [[Teilmenge]] aller verfügbaren Funktionen ist es möglich, Domänen die ihre eigenen Funktionsleerzeichen beinhalten zu erhalten. Diese Domänen erhalten also eine Funktion, die auf sie selbst angewendet werden kann. 
Neben diesen Eigenschaften ermöglicht die Bereichstheorie auch eine ansprechende, intuitive [[Interpretation]]. Wie bereits erwähnt, werden die Domänen der Berechnung immer teilweise angeordnet. Diese Reihenfolge stellt eine [[Hierarchie]] von Informationen oder Wissen dar.

''Je höher ein Element innerhalb der Ordnung ist, desto spezifischer ist es und desto mehr Informationen enthält es. In der Hierarchie unten angesiedelte Elemente repräsentieren unvollständiges Wissen oder unvollständige Zwischenergebnisse.''

Die Berechnung wird in weiterer Folge durch Anlegen monotoner Funktionen auf Elemente der Domäne wiederholt, um ein Ergebnis zu verfeinern. Das Erreichen eines festen Punktes bedeutet die  Endbearbeitung einer solchen Berechnung.

== Übersicht der formalen Definitionen ==
Dieser Abschnitt beinhaltet die zentralen Konzepte und Definitionen der Bereichstheorie.
==== Führende Sätze als konvergierende Daten ====
Die Bereichstheorie befasst sich mit Halbordnungen um die Berechnung einer Domäne zu modellieren. Das Ziel besteht darin, die Bestandteile bzw. Elemente einer solchen Reihenfolge wie Informationsteile oder Teilergebnisse einer Berechnung  so zu interpretieren, das die in der höheren Ebene angesiedelten Informationen mit den darunterliegenden Elementen einen konsistenten Weg aufweisen. Der dadurch bedingte, logische Rückschluss ergibt, dass Domänen nicht oft ein größeres Element darstellen, da dies bedeuten würde, dass es ein solches Element sämtliche Informationen aller anderen Elemente beinhaltet, was wiederum  eine  eher uninteressante Situation darstellt.

Eine wichtige Rolle bei dieser Theorie spielt die gerichtete Teilmenge einer Domäne. Das bedeutet eine nicht leere Untergruppe der betreffenden Reihenfolge in der jeweils zwei Elemente eine Obergrenze aufweisen, die für sich ein Element dieser Teilmenge darstellen. Im Hinblick auf die Intuition zu Domänen bedeutet dies, dass die oben angeführten Teile von Informationen innerhalb der höherwertigen Teilmenge konsequent durch ein anderes Element in eben dieser Teilmenge erweitert werden. Diese Interpretation kann mit dem Begriff einer [[Konvergente Folge|konvergenten Folge]] verglichen werden, wobei jedes Element spezifischer ist, als das Vorhergehende. 

''In der Alternative, der Theorie der metrischen Räume, stehen Sequenzen in vielerlei Hinsicht analog zu den Sequenzen der Bereichstheorie.''

Von der Grundidee der teilweise angegebenen Ergebnisse als Vertreter unvollständigen Wissens, wird eine andere Eigenschaft abgeleitet, die Existenz eines kleinsten Elements. Ein solches Element enthält keine Informationen, dient aber als „Ort“ an dem die meisten Berechnungen beginnen bzw als Ausgangspunkt einer Berechnung.

==== Domänenfunktionen ====
Domänen beinhalten Funktionen wie Eingänge von Berechnungen und Ausgänge von selbigen. Man geht aufgrund dieser Feststellung davon aus, dass der Ausgang einer Funktion mehr Informationen enthält, wenn der Informationsgehalt des Eingangs ebenso erweitert wird. Formal bedeutet dies, dass eine Funktion monoton sein soll.

Eine vollständige Halbordnung (CPO) ist eine Halbordnung mit einem kleinsten Element und der Eigenschaft, dass jede Teilmenge, die eine aufsteigende Kette  bildet, ein „Oberstes“ ([[Supremum]]) besitzt. Das Supremum muss dabei nicht in der Teilmenge selbst liegen. Zu beachten ist auch, dass unter Berücksichtigung der gerichteten Sätze von zwei Elementen, eine solche Funktion ebenso [[monoton]] zu sein hat. Diese Eigenschaften führen zu der Vorstellung einer Scott-stetigen Funktion.

==== Approximation und Endlichkeit ====
Die Bereichstheorie stellt einen rein qualitativen Ansatz zur Modellierung einer Struktur von Informationen und Zuständen dar. Aufgrund dieses Ansatzes wird angenommen, dass etwas mehr Informationen enthält, aber die Menge an zusätzlichen Informationen nicht angegeben ist. 

Dennoch stellen bestimmte Situationen eine Notwendigkeit dar, um über Elemente, die in einem gewissen Sinne einen viel einfacheren oder viel unvollständigeren Zustand  von Informationen beinhalten, zu sprechen. Um eine solche Beziehung zu modellieren, muss man die induzierte strenge Ordnung  (<) einer Domäne mit der Ordnung  (≤) betrachten.

==== Approximationsordnung ====
Eine aufwendigere Methode der Modellierung führt zur sogenannten [[Approximationsordnung]].  Das Element ''x'' approximiert ''y'', in Zeichen <math> x \ll y </math>, wenn für jede [[gerichteten Menge]] <math>D</math> mit <math> y \sqsubseteq \sup D </math> ein Element <math>d \in D</math> existiert mit <math> x \sqsubseteq d </math>.

Aus <math>x \ll y</math> folgt <math> x \sqsubseteq y </math>, da <math>\{y\}</math> eine gerichtete Menge ist.

Das Supremum der Kette <math> \{0\}, \{0, 1\}, \{0, 1, 2\}, \ldots </math> ist die Menge aller natürlichen Zahlen '''N''' und zeigt, dass keine unendliche Menge '''N''' approximieren kann.

==== Grundlagen von Domänen ====
Im Allgemeinen beschränkt man sich auf eine bestimmte Teilmenge von Elementen die als immer ausreichend für alle anderen Elemente als kleinste obere Schranke anzunehmen ist. Folglich definiert man die Basis der [[Korrelationsungleichung]] (Posets) '''P''' als eine Teilmenge '''B''' an '''P''' derart, dass diese für '''X''' bis '''P''', die Menge der Elemente in '''B''', die weit unter '''X''' stehen einen gerichteten Satz mit dem Supremum '''X''' enthält. 

Die Poset '''P''' ist eine kontinuierliche Korrelationsungleichung  wenn sie über eine eigene Basis verfügt. Solch ein Poset wird als [[algebraisch]] angesehen. Aus der Sicht der Funktionensemantik werden algebraische Posets besonders gut aufgenommen, da sie die Angleichung aller Elemente, auch wenn eine Beschränkung besteht, ermöglicht. Jedoch ist nicht jedes endliche Element "endlich" im klassischen Sinne, weswegen es erforderlich ist, diese Endlich-Elemente in einer unzähligen Reihe darzustellen. In manchen Fällen jedoch dienen diese Endlichen-Elemente als Basis für zählbare Posets. In diesem Fall spricht man von einem ω-kontinuierlichen Poset. Dementsprechend erhält man eine Ordnung die ω-algebraisch ist.

==== Besondere Arten von Domänen ====
Eine einfache Art einer Domäne wird als elementare oder flache Domäne bezeichnet. Diese besteht aus einem Satz von unvergleichbaren Elementen,  die insgesamt mit einem einzigen "unteren" Element betrachtet kleiner ist, als alle anderen Elemente.

Eine weitere Art von Domänen sind kontinuierliche Posets und algebraische Posets. Bei gegebener Vollständigkeit erhält man kontinuierliche Gitter und algebraische Gitter.

Die historischen Klassen von Posets, die sogenannten Scott Domains, waren die ersten Strukturen in der Bereichstheorie, die untersucht wurden. Weitere Klassen von Domänen sind SFP-Domänen und L-Domänen. 

Alle diese Klassen von Domänen können, unter Verwendung ihrer jeweiligen Funktionen, wieder in verschiedene Kategorien unterteilt werden. In monotone, Scott-kontinuierliche oder sogar spezialisierte Morphismen [[Kategorientheorie|(Kategorientheorie)]]. Letztendlich ist zu beachten, dass der Begriff Domäne selbst nicht genau definiert ist und somit nur als Abkürzung bzw. formale Definition verwendet wird.

== Siehe auch ==
* [[Scott-Topologie]]
* [[Kategorientheorie]]

== Weblinks ==
* [http://www.uni-siegen.de/fb6/tcs/team/spreen Fachgruppe für Theoretische Informatik - Universität Siegen] – deutsch
* [http://homepages.inf.ed.ac.uk/als/Research/topological-domain-theory.html Topological Domain Theory-Übersicht] - englisch
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.903 Domain Theory (1994) by Samson Abramsky] - englisch
* [http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf Domain Theory - Corrected and expanded version] (PDF, 1.06 MB) 

==  Einzelnachweise  ==
<references />

[[Kategorie:Teilgebiet der Mathematik]]