Quotients and weakly algebraic sets in pseudoeffect algebras

In the paper, we show that the quotient [E]_I[E]_I of a lattice-ordered pseudoeffect algebra EE with respect to a normal weak Riesz ideal II is linearly ordered if and only if II is a prime normal weak Riesz ideal, and [E]_I[E]_I is a representable pseudo MV-algebra if and only if II is an intersection of prime normal weak Riesz ideals. Moreover, we introduce the concept of weakly algebraic sets in pseudoeffect algebras, discuss the characterizations of weakly algebraic sets and show that weakly algebraic sets in pseudoeffect algebra EE are in a one-to-one correspondence with normal weak Riesz ideals in pseudoeffect algebra E.E.     

Riesz ideals in generalized pseudo effect algebras and in their unitizations

We prove that there is an order isomorphism between the lattice of all normal Riesz ideals and the lattice of all Riesz congruences in upwards directed generalized pseudoeffect algebras (or GPEAs, for short). We give a sufficient and necessary condition under which a normal Riesz ideal I of a weak commutative generalized pseudoeffect algebra P is a normal Riesz ideal also in the unitization [^(P)]\widehat{P} of P. These results extend those obtained recently by Avalllone, Vitolo, Pulmannová and Vinceková for effect algebras. At the same time, we give the conditions under which the quotient of a generalized pseudoeffect algebra P is a generalized effect algebra and linearly ordered generalized pseudoeffect algebra.     

由可精确测量元控制的弱可换的伪效应代数

主要研究了由可精确测量元控制的弱可换的伪效应代数中可精确测量元。证明了可精确测量元控制的弱可换的伪效应代数中可精确测量元是弱可换的伪正交代数代数。讨论了弱可换的伪效应代数与BZ-偏序集之间的关系。讨论了弱可换的伪效应代数商代数中可精确测量元与正规Riesz理想之间的关系。     

Ideals and quotients in lattice ordered effect algebras

 We show that a quotient of a lattice ordered effect algebra L with respect to a Riesz ideal I is linearly ordered if and only if I is a prime ideal, and the quotient is an MV-algebra if and only if I is an intersection of prime ideals. A generalization of the commutators in OMLs is defined in the frame of lattice ordered effect algebras, such that the quotient with respect to a Riesz ideal I is an MV-algebra if and only if I contains all generalized commutators. If L is an OML, generalized commutators coincide with the usual Marsden commutators.     

Congruences and ideals in pseudo effect algebras as total algebras

Congruences and ideals in pseudo-effect algebras and their total algebra versions are studied. It is shown that every congruence of the total algebra induces a Riesz congruence in the corresponding pseudo-effect algebra. Conversely, to every normal Riesz ideal in a pseudo-effect algebra there is a total algebra, in which the given ideal induces a congruence of the total algebra. Ideals of total algebras corresponding to lattice-ordered pseudo-effect algebras are characterized, and it is shown that they coincide with normal Riesz ideals in the pseudo-effect algebras.     

Ideals in MV-pairs

An MV-pair is a BG-pair (B, G) (where B is a Boolean algebra and G is a subgroup of the automorphism group of B) satisfying certain conditions. Recently, it was proved by Jenča that, given an MV-pair (B, G), the quotient B/~ _G , where ~ _G is an equivalence relation naturally associated with G, is an MV-algebra, and conversely, to every MV-algebra there corresponds an MV-pair. In this paper, we study relations between congruences of B and congruences of B/~ _G induced by a G-invariant ideal I of B. In addition we bring some relations between ideals in MV-algebras and in the corresponding R-generated Boolean algebras.     

Cartesian product of compressible effect algebras

In the paper, we prove that is compatible with p}, the set of commutant of p, and , the projection commutant of a, are all normal sub-effect algebras of a compressible effect algebra E, and is a direct retraction on E} is a normal sub-effect algebra of an effect algebra E. Moreover, we answer an open question in Gudder’s (Rep Math Phys 54:93–114, 2004), Compressible effect algebras, Rep Math Phys, by showing that the cartesian product of an infinite number of E _i is a compressible effect algebra if and only if each E _i is a compressible effect algebra. This work was supported by the SF of Education Department of Shaanxi Province (Grant No. 07JK267), P. R. China.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

Minimal equational representations of recognizable tree languages

 A tree language is congruential if it is the union of finitely many classes of a finitely generated congruence on the term algebra. It is well known that congruential tree languages are the same as recognizable tree languages. An equational representation is an ordered pair (E, P) , where E is either a ground term equation system or a ground term rewriting system, and P is a finite set of ground terms. We say that (E, P) represents the congruential tree language L which is the union of those ?^* _E -classes containing an element of P, i.e., for which L=⋃{[p]_? ^* _E ∣p∈P}. We define two sorts of minimality for equational representations. We introduce the cardinality vector (∣E∣, ∣P∣) of an equational representation (E, P). Let ? _l and ? _a denote the lexicographic and antilexicographic orders on the set of ordered pairs of nonnegative integers, respectively. Let L be a congruential tree language. An equational representation (E, P) of L with ? _l -minimal (? _a -minimal) cardinality vector is called ? _l -minimal (? _a -minimal). We compute, for an L given by a deterministic bottom-up tree automaton, both a ? _l -minimal and a ? _a -minimal equational representation of L. Received: 27 July 1994/5 October 1995     

A Representation Theorem for MV-algebras

An MV-pair is a pair (B,G) where B is a Boolean algebra and G is a subgroup of the automorphism group of B satisfying certain conditions. Let ~ _G be the equivalence relation on B naturally associated with G. We prove that for every MV-pair (B,G), the effect algebra B/ ~ _G is an MV-effect algebra. Moreover, for every MV-effect algebra M there is an MV-pair (B,G) such that M is isomorphic to B/ ~ _G . This research is supported by grant VEGA G-1/3025/06 of MŠ SR, Slovakia and by the Science and Technology Assistance Agency under the contract No. APVT-51-032002.     

Blocks of pseudo-effect algebras with the Riesz interpolation property

 Pseudo-effect algebras are partial algebras (E;+,0,1) with a partially defined sum + which is not necessary commutative only associative and with two complements, left and right ones. They are a generalization of effect algebras and of orthomodular posets as well as of (pseudo) MV-algebras. We define three kinds of compatibilities of elements and we show that if a pseudo-effect algebra satisfies the Riesz interpolation property, and another natural condition, then every maximal set of strongly compatible elements, called a block, is a pseudo MV-subalgebra, and the pseudo-effect algebra can be covered by blocks. Blocks correspond to Boolean subalgebras of orthomodular posets. Dedicated to Prof. Ján Jakubík on the occasion of his 80th birthday The paper has been supported by the grant VEGA 2/3163/23 SAV, Bratislava, Slovakia, and the fellowship of the Alexander von Humboldt Foundation, Bonn, Germany. The author is thankful the Alexander von Humboldt Foundation for organizing his stay at University of Ulm, Ulm, summer 2001, and Prof. G. Kalmbach H.E. for her cordial hospitality and discussions.     

On cool congruence formats for weak bisimulations

In TCS 146, Bard Bloom presented rule formats for four main notions of bisimulation with silent moves. He proved that weak bisimulation equivalence is a congruence for any process algebra defined by WB cool rules, and established similar results for rooted weak bisimulation (Milner’s “observational congruence”), branching bisimulation and rooted branching bisimulation. This study reformulates Bloom’s results in a more accessible form and contributes analogues for (rooted) η-bisimulation and (rooted) delay bisimulation. Moreover, finite equational axiomatisations of rooted weak bisimulation equivalence are provided that are sound and complete for finite processes in any RWB cool process algebra. These require the introduction of auxiliary operators with lookahead, and an extension of Bloom’s formats for this type of operator with lookahead. Finally, a challenge is presented for which Bloom’s formats fall short and further improvement is called for.     

The B<Subscript>4</Subscript>-valued propositional logic with unary logical connectives ~<Subscript>1</Subscript> / ~<Subscript>2</Subscript> /¬

A B ₄-valued propositional logic will be proposed in this paper which there are three unary logical connectives ~₁, ~₂, ¬ and two binary logical connectives ∧, ∨, and a Gentzen-typed deduction system will be given so that the system is sound and complete with B ₄-valued semantics, where B ₄ is a Boolean algebra.     

Finding concurrency-related bugs using random isolation

This paper concerns automatically verifying safety properties of concurrent programs. In our work, the safety property of interest is to check for multi-location data races in concurrent Java programs, where a multi-location data race arises when a program is supposed to maintain an invariant over multiple data locations, but accesses/updates are not protected correctly by locks. The main technical challenge that we address is how to generate a program model that retains (at least some of) the synchronization operations of the concrete program, when the concrete program uses dynamic memory allocation. Static analysis of programs typically begins with an abstraction step that generates an abstract program that operates on a finite set of abstract objects. In the presence of dynamic memory allocation, the finite number of abstract objects of the abstract program must represent the unbounded number of concrete objects that the concrete program may allocate, and thus by the pigeon-hole principle some of the abstract objects must be summary objects—they represent more than one concrete object. Because abstract summary objects represent multiple concrete objects, the program analyzer typically must perform weak updates on the abstract state of a summary object, where a weak update accumulates information. Because weak updates accumulate rather than overwrite, the analyzer is only able to determine weak judgements on the abstract state, i.e., that some property possibly holds, and not that it definitely holds. The problem with weak judgements is that determining whether an interleaved execution respects program synchronization requires the ability to determine strong judgements, i.e., that some lock is definitely held, and thus the analyzer needs to be able to perform strong updates—an overwrite of the abstract state—to enable strong judgements. We present the random-isolation abstraction as a new principle for enabling strong updates of special abstract objects. The idea is to associate with a program allocation site two abstract objects, r^\sharp{r^{\sharp}} and o^\sharp{o^{\sharp}} , where r^\sharp{r^{\sharp}} is a non-summary object and o^\sharp{o^{\sharp}} is a summary object. Abstract object r^\sharp{r^{\sharp}} models a distinguished concrete object that is chosen at random in each program execution. Because r^\sharp{r^{\sharp}} is a non-summary object—i.e, it models only one concrete object—strong updates are able to be performed on its abstract state. Because which concrete object r^\sharp{r^{\sharp}} models is chosen randomly, a proof that a safety property holds for r^\sharp{r^{\sharp}} generalizes to all objects modeled by o^\sharp{o^{\sharp}} . We implemented the random isolation abstraction in a tool called Empire, which verifies atomic-set serializability of concurrent Java programs (atomic-set serializability is one notion of multi-location data-race freedom). Random isolation allows Empire to track lock states in ways that would not otherwise have been possible with conventional approaches.     

Energy Evolution in Time-Dependent Harmonic Oscillator

The theory of adiabatic invariants has a long history, and very important implications and applications in many different branches of physics, classically and quantally, but is rarely founded on rigorous results. Here we treat the general time-dependent one-dimensional harmonic oscillator, whose Newton equation q + ω²(t)q = 0 cannot be solved in general. We follow the time-evolution of an initial ensemble of phase points with sharply defined energy E_o at time t = 0 and calculate rigorously the distribution of energy E₁ after time t = T, which is fully (all moments, including the variance μ²) determined by the first moment Ē₁. For example, μ² = E²_o[(Ē₁/E_o)² — (ω(T)/ω(0))²]/2, and all higher even moments are powers of μ², whilst the odd ones vanish identically. This distribution function does not depend on any further details of the function ω(t) and is in this sense universal. In ideal adiabaticity Ē₁ = ω(T)E_o/ω(0), and the variance μ,² is zero, whilst for finite T we calculate Ē₁, and μ² for the general case using exact WKB-theory to all orders. We prove that if ω(t)is of class ^m (all derivatives up to and including the order m are continuous) μ, ∝ T^{−(m + 1)}) whilst for the class °° it is known to be exponential μ ∝ exp(—aT).     

Unmixed-dimensional Decomposition of a Finitely Generated Perfect Differential Ideal

We present an algorithm that computes an unmixed-dimensional decomposition of a finitely generated perfect differential ideal I. Each I_iin the decompositionI  = I₁ ∩   ∩ I_kis given by its characteristic set. This decomposition is a generalization of the differential case of Kalkbrener’s decomposition. We use a different approach. The basic operation in our algorithm is the computation of the inverse of an algebraic polynomial with respect to a finite set of algebraic polynomials. No factorization is needed. Some of the main problems in polynomial ideal theory can be solved by means of this decomposition: we show how the radical membership can be decided, a characteristic set of a prime differential ideal can be selected, and the differential dimension with a parametric set of a differential ideal can be read. The algorithm has been implemented in the computer algebra system MAPLE and has been tested successfully on many examples.     

On a reduction of the interval coloring problem to a series of bandwidth coloring problems

Given a graph G=(V,E) with strictly positive integer weights ω _i on the vertices i∈V, an interval coloring of G is a function I that assigns an interval I(i) of ω _i consecutive integers (called colors) to each vertex i∈V so that I(i)∩I(j)=∅ for all edges {i,j}∈E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight δ _ij is associated with each edge {i,j}∈E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i∈V so that |c(i)−c(j)|≥δ _ij for all edges {i,j}∈E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.     

Lower bounds for the bilinear complexity of associative algebras

Let R(A) denote the bilinear complexity (also called rank) of a finite dimensional associative algebra A.?We prove that if the decomposition of into simple algebras contains only noncommutative factors, that is, the division algebra is noncommutative or . In particular, -matrix multiplication requires at least essential bilinear multiplications. We also derive lower bounds of the form essential bilinear multiplications. We also derive lower bounds of the form for the algebra of upper triangular -matrices and the algebra of truncated bivariate polynomials in the indeterminates X,Y over some field k.?A class of algebras that has received wide attention in this context con-sists of those algebras A for which the Alder—Strassen Bound is sharp, i.e., R(A) = 2dim A—t is the number of maximal twosided ideals in A. These algebras are called algebras of minimal rank. We determine all semisimple algebras of minimal rank over arbitrary fields and all algebras of minimal rank over algebraically closed fields. Received: January 12, 2000.     

L-fuzzy congruence classes in universal algebras

In this paper, we study fuzzy congruence relations and their classes; so-called fuzzy congruence classes in universal algebras whose truth values are in a complete lattice satisfying the infinite meet distributive law. Fuzzy congruence relations generated by a fuzzy relation are fully characterized in different ways. The main result in this paper is that, we give several Mal'cev-type characterizations for a fuzzy subset of an algebra $A$ in a given variety to be a class of some fuzzy congruence on $A$. Some equivalent conditions are also given for a variety of algebras to possess fuzzy congruence classes which are also fuzzy subuniverses. Special fuzzy congruence classes called fuzzy congruence kernels are characterized in a more general context in universal algebras.     

An upper bound for minimizing coefficients of dimension Kolchin polynomial

In this paper, an upper bound for minimizing coefficients of the dimension Kolchin polynomial for a subset E ⊂ ℕ₀ ^m , which depends on the maximal order of elements in E, is obtained. The minimizing coefficients are always positive; some of them are invariant and play an important role in differential algebra. As an example of application of the result obtained, an estimate for a typical differential dimension of a system of partial differential equations is obtained in the case where the orders and degrees of the equations are bounded.