The Research On The Representation Of Three Domains By Formal Concept

Domain theory,proposed by D.S.Scott in the 1970s,has provided a computational mathematical model for the denotational semantics of computer programming languages,and also has been a tie which combines order,topology and information science.On the other hand,for a better understanding of lattice structures,Formal Concept Analysis was initiated by R.Wille in the early 1980s.The basic theorem of Formal Concept Analysis has shown that the collection of all formal concepts ordered by set inclusion forms a complete lattice,called a concept lattice,and conversely every complete lattice can be obtained in this way up to isomorphism.The representation of domains by Formal Concept Analysis is to characterize domains using some special concepts of a formal context.It is well known that FS-domains,L-domains and continuous lattices are three important Cartesian closed subcategories of domains.Moreover,FS-domains and L-domains are the only two maximal Cartesian closed full subcategories of domains.Based on the representation for the category of domains in terms of Formal Concept Analysis,this thesis provides the representations of FS-domains,L-domains and continuous lattices.The organization of the dissertation is as follows:Chapter 1 is a summary of the dissertation,mainly supplies the research history and current situation of various representations for Domain theory,especially,the representation for domain theory by Formal Concept Analysis.Chapter 2 introduces the basic concepts in this dissertation,including the overview and introduction of the order structure,the domain category and the related content.Chapter 3 establishes the relationship between FS-domains and FS-formal contexts.First,we present the notion of a G-formal connection among the continuous formal contexts,and introduce the notion of an FS-formal context.Every FS-formal context is a continuous formal context,whose FS-formal concepts ordered by set conclusion form an FS-domain.Second,for a given FS-domain,we show that the induced continuous formal context is an FS-formal context,and the FS-domain,formed by the FS-formal concepts of the induced FS-formal context,is isomorphic to the given FSdomain.Thus we obtain the representation theorem of FS-domains by Formal Concept Analysis.From the view of category,this realizes the characterization for FS-domains at the level of objects.Finally,we show that FS-formal contexts with G-formal connections form a category,and this category is equivalent to that of FS-domains.These results specify the presentation theory of continuous domains by Formal Concept Analysis to the category of FS-domains.Chapter 4 describes the characterization of L-domains by Formal Concept Analysis.We define and discuss an F-sup of A,where F is a consistent selection of a continuous formal context and A is a finite set of attributes.It is a local supremum of A in some sense.Based on the existence of an F-sup of A,we introduce the notion of an LDF-formal context and show that there is a one-to-one correspondence between LDFcontexts and L-domains.In addition,we also propose the notion of an F-morphism,which can be used to characterize Scott-continuous functions between L-domains.This induces a category of LDF-formal contexts which is equivalent to that of L-domains.Chapter 5 discusses the representation of continuous lattices by CL-formal contexts.This is motivated by the representation of algebraic lattices by closure spaces.We introduce the notion of a CL-formal context by adding some conditions into a continuous formal context.Using the Knaster-Tarski fixed point theorem,we give a new method of representing continuous lattices in the sense that the set of all CL-formal concepts of a CL-formal context forms a continuous lattice and each continuous lattices can be generated by a CL-context.In order to capture the Scott-continuous functions between continuous lattices,we define the notion of a G-continuous connection between CL-contexts.Then the equivalence between the category of CL-formal contexts with Gcontinuous connections and that of continuous lattices with Scott continuous functions is established.The above results demonstrate the great capacity of Formal Concept Analysis in reconstructing various subclasses of domains.The conclusion part summarizes some basic results and follow-up prospects.