Assignment Algebra Split Algorithm Hidden Semi-ring Assignment

Now it is in a period of information explosion. As a result, information is being equipped with some new characteristics such as large quantity of data, wide sources and uncertainty. It requires not only integrating different information together ef-ficiently but also focusing information into a certain point. Valuation algebra is an axiomatized framework closely related with information processing. It derives from an abstraction of the independence structure between variables in probability theory and the belief functions in the theory of evidence. Many research principles includ-ing relation algebras, expert systems, propositional logic, Bayesian Network and constraint satisfaction problems can be regarded as instances of valuation algebras. Valuation algebra deals with information mainly by the combination operation and projection operation. Its efficiency is ensured by the local computation model. The axiomatized research method helps the understanding of the essence and avoiding unnecessary duplicated work. Therefore, it remains one of the main tasks to study the properties of this framework. The splitting algorithm proposed in this paper can strengthen this framework and make the structure of local computation more clear. This algorithm is up-down and can be applied into the study of quantitative logic, soft constraint satisfaction problems and so on.In valuation algebras, the kind of valuations induced by semirings is very im-portant. This paper comes up with implicit valuations within semiring-valued ones. Due to certain reasons, such valuation's definition functions are not explicit. For instances, implicit constraints are constructed with explicit constraints by logical connectives. Propositional formulas can induce semiring-valued propositional valua-tions. What's more, the grammar constraints and soft sets, which attract researcher' s interest in recent years, can also be instances of implicit semiring-valued valuations. So, how to make implicit valuations and their operations explicit is an important work. On the other hand, the implicit representation is very useful when facing with large scale question. For example, there exists some method to represent the classical constraint problem with finite automaton. In this paper, we have proposed some practical valuation instances and their properties, discussed the methods for making implicit valuations explicit and implicit representations.There are 5 chapters in this paper.Chapter 1 makes an introduction of semirings, propositional logic, constraint satisfaction problem, grammar in theoretical computer and soft set theory, which are preliminaries needed for readersChapter 2 presents the Markov Combination Axiom and splitting algorithm. First of all, the Markov Combination Axiom is proposed in labeled valuation al-gebras, label-free valuation algebras, information algebra and semiring-valued con-straint satisfaction problems. Different forms of the Markov Combination Axiom are discussed in several transformations such as variable elimination, vacuous valuation. transportation and homomorphisms. Its relationship with conditional independence is given. Then, by the Markov Combination Axiom, some concepts including t partition, t factorization, t splitting and transitive splitting are developed, splitting algorithm for single query marginalization problem is obtained. Its relationship with collect algorithm is discussed. After that, we initially propose the idea of dynamic splitting algorithm. Covering join trees are used for showing the dynamic effects. Finally, we investigate the splitting algorithm's use for the approximate computation in valuation algebras.Chapter 3 mainly discusses the implicit valuations and instances. It is consisted of 5 sections. In the first section, the concept for implicit valuations are given. In section 2, Firstly, by semantical method, every propositional logic can be treated as implicit valuations. Then the concept of projection degree of two-valued proposi-tional formulas are derived. Its properties are considered. Especially, it is pointed out that the projection degree of the same formula is monotone decreasing with the corresponding projection domain. In section 3, semiring-valued grammar constraint satisfaction problem model is proposed as an extension of the classical grammar constraint. In section 4, semiring-valued soft set model is constructed. In addition, the operations and decision methods of semiring-valued soft sets are studied. Then the relationship between soft sets and valuation algebras are discussed. The section 5 introduces the method for automaton representation of the classical constraints. This provides a foundation for later research.Chapter 4 emphases on the application of splitting algorithms. There are two parts. The main idea of part 1 is to use the splitting algorithm into the computation problems in quantitative logic. Upon the above preparation, the splitting algorithm is used to give instructions on the computation of truth degree, D-degree, absolute degree and maximal values of semantical functions of certain types of propositional formulas. In the second section, we propose a splitting method for general automa-ton representation of semiring-valued constraints, with which the complexity for automaton representation can be reduced efficiently. Chapter 5 mainly deals with the expliciting of operations of implicit valuations. It consists of 2 sections. In the firs one, for single projection of implicit grammar constraint valuations, three kinds of algorithms are given based on CYK, decom-posable negation norm form(DXNF) and valued negation normal form (VNNF) respectively. The DNNF and VNXF methods turn the semiring-valued grammar constraint satisfaction problem into questions in the principle of DNNF and VNXF. There exist three advantages for doing this way:it provides a unified framework for different requirements; the amount of operations on-line can be reduced so that the customers can avoid useless waiting time:for the combination of grammar con-straint and prepositional constraint, this method implies a good direction. Then, with the conjunction of grammar constraint and relation constraint, algorithm for satisfiability and generalized arc consistency is given. This algorithm try to embed the relation constraint to the process of CYK algorithm. After that, the concept of grammar consequence is developed and an algorithm for satisfiability based on the Pumping lemma is proposed. The final section are about the decision making meth-ods under incomplete semiring-valued soft set valuations. Firstly, the incomplete degree and its property are discussed. Then the concept of completions and their characterization are proposed. After that, some basic methods for decision making are given. Finally, from the point of cost, a partial completion strategy is developed.