Galois Connections and Fixed Point Calculus

《Galois Connections and Fixed Point Calculus》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、GaloisConnectionsandFixedPointCalculusRolandBackhouse∗October15,2001AbstractFixedpointcalculusisaboutthesolutionofrecursiveequationsde˛nedbyamonotonicendofunctiononapartiallyorderedset.Thistutorialpresentstheba-sictheoryof˛xedpointcalculustogetherwith

2、anumberofapplicationsofdirectrelevancetotheconstructionofcomputerprograms.ThetutorialalsopresentsthetheoryandapplicationofGaloisconnectionsbetweenpartiallyorderedsets.Inpar-ticular,theintimaterelationbetweenGaloisconnectionsand˛xedpointequationsisampl

3、ydemonstrated.∗SchoolofComputerScienceandInformationTechnology,UniversityofNottingham,NottinghamNG81BB,England12Contents1Introduction41.1FixedPointEquations.............................41.2Languages....................................41.3Functions....

4、................................51.4Datatypes....................................61.5GaloisConnections...............................61.6BasicAssumptions...............................61.7IssuesandApplications............................72GaloisConnec

5、tions—IntroductoryExamples82.1SimpleExamples................................82.2TheFloorFunction...............................112.2.1PropertiesofFloor...........................122.2.2RoundingO¸..............................133AbstractPropertiesofGal

6、oisConnections163.1CombiningGaloisConnections........................163.2Cancellation...................................183.3PointwiseOrdering...............................183.4PosetIsomorphism...............................193.5UniquenessofAdjoints

7、.............................213.6UniversalProperty...............................213.7CommutativityProperties...........................234ExistenceofGaloisConnections254.1In˛maandSuprema..............................264.1.1In˛maandCompleteness......

8、.................264.1.2ShapePosets..............................284.1.3SupremaandCocompleteness.....................294.2ExtremumPreservationProperties......................304.3ExistenceTheorem...............................324.3.1PairAlgebr