Notes on Partially-Ordered Structures in Computer Science: I. PA-Ordered Semirings and Some Related Structures

Dragos Vaida (Department of Fundamentals of Computer Science, University of Bucharest, Romania)

Abstract: While the existence of inverses is a natural condition in Algebra it is seldom satisfied in Computer Science applications. Since the group-theoretical orientation has to be abandoned we consider an advantage when the non-conventional structures needed are linked to an already existing knowledge. We propose semirings as a candidate and we aim at the Computer Science applications such as processes semantics, parallel composition, Fuzzy Theory, images ordering or MV-algebras. After the definition of pa-ordered semiring four typical examples are given. Some results concerning additively idempotent semirings are extended to monoids considered as their natural background. A direct sum representation is given for lower semilattice-ordered Gelfand semirings s-ordered. A sufficient condition is given for having the natural quasi-order an s-order. A multiplicative ordering is built up and its application to Visual Data is indicated. Wrt complements in pa-semirings we give sufficient conditions for the existence of some sums and for commutativity.

Keywords: quasi-order, s-order, semiring

Categories: F.4.1