Additive functions and their application to uncertain information

For additive functions over ordered sets, a minimum representation is given in case the ordered set has a particular deviation property. Additive functions are known to be special supermodular functions on power sets and in probability calculus, they are related to, for example, capacities and distribution functions of random sets. Their capability to encode vague information is stressed.     

Directed complete poset congruences

The study of algebraic properties of ordered structures has shown that their behavior in many cases is different from algebraic structures. For example, the analogues of the fundamental mapping theorem for sets which characterizes surjective maps as quotient sets modulo their kernel relations, is not true for order-preserving maps between posets (partially ordered sets). The main objective of this paper is to study the quotients of dcpos (directed complete partially ordered sets), and their relations with surjective dcpo maps (directed join preserving maps). The motivation of studying such infinitary ordered structures is their importance in domain theory, a theory on the borderline of mathematics and theoretical computer science.In this paper, introducing the notion of a pre-congruence on dcpos (directed complete partially ordered sets), we give a characterization of dcpo congruences. Also, it is proved that unlike natural dcpo congruences, the dcpo congruences are precisely kernels of surjective dcpo maps. Also, while it is known that the image of a dcpo map is not necessarily a subdcpo of its codomain, we find equivalent conditions on a dcpo map to satisfy this property. Moreover, we prove the Decomposition Theorem and its consequences for dcpo maps.     

Diagonal fixed points in algebraic recursion theory

The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those produced by the Curry combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement of the axiomatization of recursion theory via combinatory spaces. Supported in part by the Ministry of Education and Science of Republic of Bulgaria, contract No 705     

Quantum stochastic calculus

An introduction to quantum stochastic calculus in symmetric Fock spaces from the point of view of the theory of stochastic processes. Among the topics discussed are the quantum Itô formula, applications to probability representation of solutions of differential equations, extensions of dynamical semigroups. New algebraic expressions are given for the chronologically ordered exponential functions generated by stochastic semigroups in classical probability theory.Translated from Itogi Nauki i Tekhniki, Seriya Sovremennye Problemy Matematiki, Noveishie Dostizheniya, Vol. 36, pp. 3–28, 1990.     

Objective Bayesian probabilistic logic

This paper develops connections between objective Bayesian epistemology—which holds that the strengths of an agent's beliefs should be representable by probabilities, should be calibrated with evidence of empirical probability, and should otherwise be equivocal—and probabilistic logic. After introducing objective Bayesian epistemology over propositional languages, the formalism is extended to handle predicate languages. A rather general probabilistic logic is formulated and then given a natural semantics in terms of objective Bayesian epistemology. The machinery of objective Bayesian nets and objective credal nets is introduced and this machinery is applied to provide a calculus for probabilistic logic that meshes with the objective Bayesian semantics.     

Non-Unit Free Triangle Orders

A Free Triangle order is a partially ordered set in which every element can be represented by a triangle. All triangles lie between two parallel baselines, with each triangle intersecting each baseline in exactly one point. Two elements in the partially ordered set are incomparable if and only if their corresponding triangles intersect. A unit free triangle order is one with such a representation in which all triangles have the same area. In this paper, we present an example of a non-unit free triangle order.     

A partial order generalization of Alexander's subbase theorem

Alexander's Subbase Theorem is generalized for partially ordered sets. Our generalization is nontrivial inasmuch as Alexander's Theorem pertains to the partially ordered set (T, ∪) whereT is the set of all the open sets of a topological space and thus \((\overline T ,\underline C )\) is a complete partially ordered set which is also join infinite distributive, whereas here our generalization pertains to any partially ordered set with a maximum 1 and which satisfies the rather weak «distributivity» condition given by (1) below.     

Categorical Abstract Algebraic Logic: Subdirect Representation of Pofunctors

Pa?asińska and Pigozzi developed a theory of partially ordered varieties and quasi-varieties of algebras with the goal of addressing issues pertaining to the theory of algebraizability of logics involving an abstract form of the connective of logical implication. Following their lead, the author has abstracted the theory to cover the case of algebraic systems, systems that replace algebras in the theory of categorical abstract algebraic logic. In this note, an order subdirect representation theorem for partially ordered algebraic systems is proven. This is an analog of the Order Subdirect Representation Theorem of Pa?asińska and Pigozzi, which, in turn, generalizes the well-known Subdirect Representation Theorem of Universal Algebra.     

Graphs realised by r.e. equivalence relations

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.     

A partition relation for partially ordered sets

We introduce a partition relation which is an alternate for measuring how badly the ordinary partition relation fails, we develop its corresponding partition calculus and we determine its status for various typical partially ordered sets.     

Algorithms over partially ordered sets

We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.     

The fundamental duality of partially ordered sets

The representation of partially ordered sets by subsets of some set such that specified joins (meets) are taken to unions (intersections) suggests two categories, that of partially ordered sets with specified joins and meets, and that of sets equipped with suitable collections of subsets, and adjoint contravariant functors between them. This, in turn, induces a duality including, among several others, the two Stone Dualities and that between spatial locales and sober spaces.     

Fuzzy sets and type 2 under algebraic product and algebraic sum

The concept of fuzzy sets of type 2 has been proposed by L.A. Zadeh as an extension of ordinary fuzzy sets. A fuzzy set of type 2 can be defined by a fuzzy membership function, the grade (or fuzzy grade) of which is taken to be a fuzzy set in the unit interval [0, 1] rather than a point in [0, 1].This paper investigates the algebraic properties of fuzzy grades (that is, fuzzy sets of type 2) under the operations of algebraic product and algebraic sum which can be defined by using the concept of the extension principle and shows that fuzzy grades under these operations do not form such algebraic structures as a lattice and a semiring. Moreover, the properties of fuzzy grades are also discussed in the case where algebraic product and algebraic sum are combined with the well-known operations of join and meet for fuzzy grades and it is shown that normal convex fuzzy grades form a lattice ordered semigroup under join, meet and algebraic product.     

Updating credal networks is approximable in polynomial time

Credal networks relax the precise probability requirement of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper, we present a new variable elimination algorithm for exactly computing posterior inferences in extensively specified credal networks, which is empirically shown to outperform a state-of-the-art algorithm. The algorithm is then turned into a provably good approximation scheme, that is, a procedure that for any input is guaranteed to return a solution not worse than the optimum by a given factor. Remarkably, we show that when the networks have bounded treewidth and bounded number of states per variable the approximation algorithm runs in time polynomial in the input size and in the inverse of the error factor, thus being the first known fully polynomial-time approximation scheme for inference in credal networks.     

On coincidences of families of mappings on ordered sets

New results on fixed points and coincidences of families of set-valued mappings of partially ordered sets obtained without commutativity assumptions are presented. These results develop theorems on fixed points of an isotone self-mapping of an ordered set (for families of set-valued mappings) and theorems about coincidences of two set-valued mappings one of which is isotone and the other is covering (for finite families of set-valued mappings).     

Warped MPDAE Models including Minimisation Criteria for the Simulation of RF Signals

In radio frequency (RF) applications, electric circuits produce signals including widely separated time scales. A multidimensional representation yields an efficient model by decoupling the time scales. Consequently, a warped multirate partial differential algebraic equation (MPDAE) describes the circuit's behaviour. The appropriate determination of an arising local frequency function is crucial for the efficiency of this approach. Variational calculus implies a necessary condition to a specific solution, which exhibits a minimal amount of oscillations in the whole domain of dependence. We apply a similar strategy to minimise oscillatory performance in some boundary values only. Now variational calculus yields a boundary condition, which can easily be used in numerical methods. We compare the results of both minimisation criteria in a simulation of a warped MPDAE model. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

On SIP algorithms for minimizing the mean-risk function in the multi-period single-source problem under uncertainty

We present an algorithmic framework for solving the strategic problem of assigning retailers to facilities in a multi-period single-sourcing product environment under uncertainty in the demand from the retailers and the costs of production, inventory holding, backlogging and distribution of the product. The functional to minimize is included by the expected objective function and the excess probability functional. By considering a splitting variable mathematical representation of the Deterministic Equivalent Model, we introduce several so-called Fix-and-Relax procedures that exploit the excess probability functional structure in addition to the structure of the special ordered sets related to the non-anticipativity constraints for the assignment variables. Some computational experience is reported. This research has been partially supported by the Grant TIC2003-05982-C05-05 from MCYT.     

Reduced sub-powers and the decision problem for finite algebras in arithmetical varieties

The aim of this paper is to prove that every finitely generated, arithmetical variety of finite type, in which every subdirectly irreducible algebra has linearly ordered congruences has a decidable first order theory of its finite members. The proof is based on a representation of finite algebras from such varieties by some quotients of special subdirect products in which sets of indices are partially ordered into dual trees. Then the result of M. O. Rabin about decidability of the monadic second order theory of two successors is applied.Presented by Stanley Burris.     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.