International Journal of Algebra and Computation

Revision and update operators add new information to some old information represented by a logical theory. Katsuno and Mendelzon show that both revision and update operators can be characterized as accomplishing a minimal change in the old information to accommodate the new information. Arbitration operators add two or more weighted informations together where the weights indicate the relative importance of the informations rather than a strict priority. This paper shows that arbitration operators can be also characterized as accomplishing a minimal change. The operator of model-fitting is also defined and analyzed in the paper.

The present paper is devoted to some aspects of postian matrix theory over an arbitrary Post algebra, through results in Postian relative–pseudocomplementation. It is well known (for instance Rousseau [10] or Dwinger [6]) that any r-Post algebra is a Brouwerian lattice (or a Heyting algebra), that is to say, for every (a, b) in P², the set of x in P such as a. x ≤ b admits a greatest element (a.x is inf{a, x}), called the relative inf–pseudocomplement of a in b, and denoted (b|a). In the first part of our paper, we compute the explicit expression of the disjunctive components of the relative inf–pseudocomplement (Theorem 2), which allows us to state some specific new properties of Postian pseudocomplementation, among which the cases where (b|a) is a Boolean element, and the equation (x|a) = c (Theorem 4), for which we give a consistency condition. Relative pseudo complementation in fact plays a major role in Postian structures, since we show (Theorem 5), that every element a in P is completely determined by the sequence of the (e_k|a): in fact, being given (r-1) elements of P submitted to the ascending chain condition: α₁ ≤ α₂ ≤ … ≤ α_r-1, there exists exactly one a in P such as (e_k|a) = α_k for every k, where the e_k are the elements of the underlying chain in P. Study of pseudocomplementation properties in some Post algebra P actually helps us to enlighten relations between P and, on one hand, its center B (the set of its complemented elements, which is a Boolean algebra), on the other hand, the underlying chain.

The second part is devoted to Postian linear matrix equations and inequations: in fact just like in Boolean algebras, the existence of the inf–pseudocomplement in the underlying lattice implies the residuation property is valid over the ordered semi-group of Postian matrices, equipped with the matrix product ⊗ (this was a general theorem from Blyth [3]): the Postian matrix inequation A ⊗ X ≤ B thus admits a greatest solution (Theorem 6), which is explicitly computed. This provides a consistency condition for the matrix equation A ⊗ X = B (Theorem 7).

Another result states a characterization of inversible square Postian matrices. On this point of inversibility, as it is well known, the Boolean results were built in three successive steps by Wedderbrun [17], Luce [9] and Rutherford [13]. As to the Postian case, we prove in turn that a Postian matrix is inversible if and only if it is Boolean and orthogonal (Theorem 11). To prove this result, as well as Theorem 2 in the first part, we make a systematic use of the representation theorem for Post algebras by the Boolean way, as enunciated in the Preliminaries (Theorem 1). Repeated applications of the method provide a large set of conditions equivalent to the inversibility of a Postian matrix (Theorem 12).

Afterwards, we examine various other Postian matrix equations and inequations, among which ^t A ⊗ A ≤ I, leading to the characterization of right–distributive over conjunction–Postian matrices (Theorem 9), and also the equation A ⊗ X = E_k, for which it is given a complete consistency condition (Theorem 13).

Noncommutative analogues of classical operations on symmetric functions are investigated, and applied to the description of idempotents and nilpotents in descent algebras. It is shown that any sequence of Lie idempotents (one in each descent algebra) gives rise to a complete set of indecomposable orthogonal idempotents of each descent algebra, and various deformations of the classical sequences of Lie idempotents are obtained. In particular, we obtain several q-analogues of the Eulerian idempotents and of the Garsia-Reutenauer idempotents.

We give a simple proof of a sufficient condition for an amalgamated free product of two negatively curved groups to be negatively curved, and we compute the curvature of such products.