Assignment Algebra

Valuation algebra is an algebraic structure for permitting local computation of non-deterministic information, which is abstracted from many theoretical for-malisms including soft constraints, relation databases, belief functions and so on. Recent research demonstrates that many important instances such as constraint sys-tem, possibility potential, and probability potential can be induced by some special semirings. In this paper, we mainly study the issue about the optimal solutions of projection problems in semiring-induced valuation algebras, the structures of valu-ation algebras and the relationship among them. In the study on optimal solutions of projection problems, we give the conditions of mappings preserving optimal so-lutions. These conclusions provide a basis for finding out some suitable transitive mappings. By the study on the structures of valuation algebras, we realize the re-lationship among valuation algebras with different structures and the relationship between semiring-induced valuation algebras and semirings. We present an example of labeled compact information algebra, and therefore take the set of all soft sets over a universal set as a research object of information algebras firstly.The main contributions in this thesis are listed as follows:(1) Projection problems on semiring-induced valuation algebras:Projection problems over valuation algebras focus on the corresponding information which is obtained in a local domain of valuations. Firstly, solution-order and problem-order on projection problems of semiring-induced valuation algebras are defined. The rela-tionship among orderings, and the relationship among mappings that preserve these orderings are discussed respectively. For a transitive surjective f between two semir-ings, it preserves the solution-order if and only if it is a semiring homomorphism. By using constructive methods, some sufficient conditions of mapping preserving optimal solutions of projection problems are given. The relationship between map-pings preserving the optimal solutions and its preserving the solution-order relation is studied. It is shown that if there exist at least four variables in a system and one of frames includes more than two elements, then a surjective f preserves the optimal solutions of projection problems and preserves the zero element, the unit element of semiring if and only if f is order-reflecting with respective to the order relation on semiring and preserves the solution-order of projection problems.(2) Solution configurations and solution extensions of valuations:It is shown that, for a valuation induced by a totally ordered semiring, the set of its solution configurations will not be changed if the transitive mapping preserves the plus operation. The expression of the maximal value for projection problem is given. The theorem of solution extension of valuations under a weaker condition is presented.(3) Homomorphism of valuation algebras:The relationship on algebraic struc-ture between semirings and semiring-induced valuation algebras is studied. It is shown that the isomorphism between semiring-induced valuation algebras is a nec-essary condition of the isomorphism between semirings, and also a necessary condi-tion of the isomorphism between multiplicative semigroups of semirings. A general valuation homomorphism based on different domains is defined, and the Homomor-phism Theorem of valuation algebra is proved.(4) The properties of two types of continuous information algebras and the relationship between them:The continuity and strong continuity in information algebras are introduced respectively. By studying the relationship between domain-free information algebras and labeled information algebras, it is demonstrated that they do correspond to each other on continuity. A more general notion of con-tinuous function which is defined between two domain-free continuous information algebras is presented. It is shown that the set of all continuous functions between s-continuous information algebras forms a new s-continuous information algebra.(5) The methods of obtaining compact information algebras and the properties of the related category:The definition of labeled strongly compact information alge-bra is given. It is shown that there exist complete correspondences between labeled information algebras and domain-free information algebras with respect to the com-pactness and strong compactness. Two methods of obtaining compact information algebras are presented. It is shown that a domain-free information algebra induced by a semiring is compact, if the semiring is an algebraic lattice with respect to the converse order relation. Next, an approach to realize the compactification of a gen-eral domain-free information algebra is offered. It is shown that the two categories of strong compact information algebras and strong continuous information algebras are Cartesian closed.(6) An example of labeled compact information algebra:A new kind of order relation on fuzzy soft sets, called soft information order, is introduced. It is shown that the collection of all fuzzy soft sets (over a given soft universe), equipped with this new order, forms a completely distributive lattice. With the operations of la-beling, extended intersection and projection, it is also a labeled information algebra. It is declared that the set of all soft sets, which have finite parameters set, is formed a labeled strongly compact information algebra.