The greedy algorithm for partially ordered sets

Those independence systems on finite partially ordered sets are characterized for which the greedy algorithm always works.     

An analysis of the greedy algorithm for partially ordered sets

The worst-case analysis of the greedy algorithm for a combinatorial problem of linear maximization on a partially ordered set (introduced by U. Faigle [3]) is given.     

Searching for partially ordered structures

General methods are developed to search for minimal and dead-end payoff operators for a class of sources endowed with a partial order structure. It is shown that the results can be used in the design of experiments with automata and in the minimization of Boolean functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 2, pp. 253–260, February, 1992.     

Completions for partially ordered semigroups

A standard completion γ assigns a closure system to each partially ordered set in such a way that the point closures are precisely the (order-theoretical) principal ideals. If S is a partially ordered semigroup such that all left and all right translations are γ-continuous (i.e., Y∈γS implies {x∈S:y·x∈Y}∈γS and {x∈S:x·y∈Y}∈γS for all y∈S), then S is called a γ-semigroup. If S is a γ-semigroup, then the completion γS is a complete residuated semigroup, and the canonical principal ideal embedding of S in γS is a semigroup homomorphism. We investigate the universal properties of γ-semigroup completions and find that under rather weak conditions on γ, the category of complete residuated semigroups is a reflective subcategory of the category of γ-semigroups. Our results apply, for example, to the Dedekind-MacNeille completion by cuts, but also to certain join-completions associated with so-called “subset systems”. Related facts are derived for conditional completions. A first draft of this paper by the second author, containing parts of Section 2, was received on August 9, 1985.     

A construction for partially ordered sets

A construction I(S) is defined which corresponds to the intuitive notion of the set of places in which new elements can be inserted into a given poset S. It is given the minimal possible ordering. It turns out that if the base sets are chains the construction produces the corresponding interval orders. for whose dimensions there exist good estimates. In this paper we make the dual restriction that the height of the underlying set is ?1. Under this assumption we find a bound for the dimension of I(S) in general and a precise value if the set consists of two antichains all the elements of one lying above all those of the other.     

Component partially ordered sets

Properties of component partially ordered sets (i.e., dense subsets of Boolean algebras) are used to construct mappings of Boolean algebras generalizing the idea of homomorphisms; the properties of a minimal Boolean algebra generated by a given component partially ordered set are investigated.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 275–283, March, 1971.     

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.     

Fully ordered groups in partially ordered linear algebras

No abstract. Received September 2, 1999; accepted in final form October 23, 2000.     

Quasimartingales on partially ordered sets

The concept of a quasimartingale, and therefore also of a function of bounded variation, is extended to processes with a regular partially ordered index set V and with values in a Banach space. We show that quasimartingales can be described by their associated measures, defined on an inverse limit space $\text{S × Ω}$ containing $\text{V × Ω}$, furnished with the σ-algebra $\text{P}$ of the predictable sets. With the help of this measure, a Rao-Krickeberg and a Riesz decomposition is obtained, as well as a convergence theorem for quasimartingales. For a regular quasimartingale X it is proven that the spaces ($\text{S × Ω}$, $\text{P}$) and the measures associated with X are unique up to isomorphisms. In the case V = $\text{R}$₊ⁿ we prove a duality between classical (right-) quasimartingales and left-quasimartingales.     

Division closed partially ordered rings

Fuchs called a partially-ordered integral domain, say D, division closed if it has the property that whenever a > 0 and ab > 0, then b > 0. He showed that if D is a lattice-ordered division closed field, then D is totally ordered. In fact, it is known that for a lattice-ordered division ring, the following three conditions are equivalent: a) squares are positive, b) the order is total, and c) the ring is division closed. In the present article, our aim is to study \({\ell}\)-rings that possibly possess zerodivisors and focus on a natural generalization of the property of being division closed, what we call regular division closed. Our investigations lead us to the concept of a positive separating element in an \({\ell}\)-ring, which is related to the well-known concept of a positive d-element.     

Representation of partially ordered sets

It is well known [1] that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, (–) such that the supremum and the infimum of any finite setF ofp correspond, respectively, to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomorphic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI. Presented by R. Freese.