Search

A proper (simple) relation algebra is a collection A of binary relations on a set U such that the top element of the algebra is U × U , and A is closed under union, intersection, complementation, composition, converse and contains the identity relation on U. Proper relation algebras can be constructed using U = Z / p Z as a base set using a method due to Comer. The cycle structure of such an algebra must, in general, be determined a posteriori , normally with the aid of a computer. In this paper, we give an improved algorithm for checking the cycle structure that reduces the time complexity from O (p 2) to O (p). [ABSTRACT FROM AUTHOR]

Abstract Binary Constraint Problems have traditionally been considered as Network Satisfaction Problems over some relation algebra. A constraint network is satisfiable if its nodes can be mapped into some representation of the relation algebra in such a way that the constraints are preserved. A qualitative representation ϕ is like an ordinary representation, but instead of requiring that (a ; b) ϕ is the composition a ϕ ∘ b ϕ of the relations a ϕ and b ϕ , as we do for ordinary representations, we only require that c ϕ ⊇ a ϕ ∘ b ϕ ⇔ c ≥ a ; b , for each c in the algebra. A constraint network is qualitatively satisfiable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfiable then it is clearly qualitatively satisfiable, but the converse can fail, as we show. However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfiable if and only if it is qualitatively satisfiable. Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over non-associative algebras. We prove that computationally, qualitative representations have many advantages over ordinary representations: whereas many finite relation algebras have only infinite representations, every finite qualitatively representable algebra has a finite qualitative representation; the representability problem for (the atom structures of) finite non-associative algebras is NP-complete ; the network satisfaction problem over a finite qualitatively representable algebra is always in NP ; the validity of equations over qualitative representations is co-NP-complete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebras. [ABSTRACT FROM AUTHOR]

Abstract A relation algebra is called measurable when its identity is the sum of measurable atoms, where an atom is called measurable if its square is the sum of functional elements. In this paper we show that atomic measurable relation algebras have rather strong structural properties: they are constructed from systems of groups, coordinated systems of isomorphisms between quotients of the groups, and systems of cosets that are used to “shift” the operation of relative multiplication. An atomic and complete measurable relation algebra is completely representable if and only if there is a stronger coordination between these isomorphisms induced by a scaffold (the shifting cosets are not needed in this case). We also prove that a measurable relation algebra in which the associated groups are all finite is atomic. [ABSTRACT FROM AUTHOR]

Abstract: In social choice theory the Banks set is a well-established choice set for tournaments that consists of the undominated elements of the maximal subtournaments. For non-complete dominance relations J. Duggan proposed three possibilities to modify it. We develop relation-algebraic specifications to compute the Banks set, Duggan’s modifications, and variants of them. All these specifications are algorithmic and can directly be translated into the programming language of the computer algebra system RelView. We show that the system is well suited for computing and visualizing the Banks set, its modifications, and the objects to be associated with them. [Copyright &y& Elsevier]

Abstract: We describe a simple computing technique for solving independence and domination problems on rectangular chessboards. It rests upon relational modeling and uses the BDD-based specific purpose computer algebra system RelView for the evaluation of the relation-algebraic expressions that specify the problems’ solutions and the visualization of the computed results. The technique described in the paper is very flexible and especially appropriate for experimentation. It can easily be applied to other chessboard problems. [Copyright &y& Elsevier]

Abstract: More than 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations of dipole calculi. This new method, which we call condensed semantics, is based on an abstract symbolic model of a specific fragment of our domain. It is based on the fact that qualitative dipole relations are invariant under orientation preserving affine transformations. The dipole calculi allow for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of dipole calculi. We integrate our results into two reasoning tools which are publicly available. [Copyright &y& Elsevier]

Abstract: Forming closures of subsets of a set X is a technique that plays an important role in many scientific disciplines and there are many cryptomorphic mathematical structures that describe closures and their construction. One of them was introduced by Aumann in the year 1970 under the name contact relation. Using relation algebra, we generalize Aumann’s notion of a contact relation between X and its powerset and that of a closure operation on from powersets to general membership relations and their induced partial orders. We also investigate the relationship between contacts and closures in this general setting and present some applications. In particular, we investigate the connections between contacts, closures and topologies and use contacts to establish a one-to-one correspondence between the column intersections space and the row intersections space of arbitrary relations. [Copyright &y& Elsevier]

Abstract: In this paper, we are concerned with a special timetabling problem. It was posed to us by the administration of our university and stems from the adoption of the British-American system of university education in Germany. This change led to the concrete task of constructing a timetable that enables the undergraduate education of secondary school teachers within three years in the “normal case” and within four years in the case of exceptional combinations of subjects. We develop two relation-algebraic models of the timetabling problem and in each case algorithms for computing solutions. The latter easily can be implemented in the Kiel RelView tool showing that RelView can be used for timetabling. [ABSTRACT FROM AUTHOR]

Abstract: Basic concepts of classical dynamics are analysed in the simple mathematical setting of state transition systems, where both time and space are discrete, and no structure is assumed on the state space besides a binary transition relation. This framework proves useful to the dynamical analysis of computations and biomolecular processes. Here a relational formulation of this framework is presented, where the concepts of attractor and recurrence surface in two variants, respectively relating to the two fundamental modalities. A strong link between recurrence and both existence and extent of attractors, in either variant, is established by a novel characterization theorem. Further concepts are easily casted in the relational language, such as product dynamics and projections thereof, which support analysis and reasoning about metabolic P systems. An outline of possible applications and future developments of this work concludes the article. [Copyright &y& Elsevier]

Abstract: Based on a set of criteria and a measuring lattice, we introduce relational measures as generalizations of fuzzy measures. The latter have recently made their way from the interval to the ordinal or even to the qualitative level. We proceed further and introduce relational measures and relational integration. First ideas of this kind, but for the real-valued linear orderings stem from Choquet (1950s) and Sugeno (1970s). We generalize to not necessarily linear orders and handle it algebraically and in a point-free manner. We thus open this area of research for treatment with theorem provers which would be extremely difficult for the classical presentation of Choquet and Sugeno integrals. Our specification of the relational integral is operational. It can immediately be translated into the programming language of RelView and, hence, the tool can be used for solving practical problems. [Copyright &y& Elsevier]

Entity-Relationship (ER) modelling is a popular technique for data modelling. Despite its popularity and widespread use, it lacks a firm semantic foundation. We propose a translation of an ER-model into relation algebra, suggesting that this kind of algebra does provide suitable mechanisms for establishing a formal semantics of ER modelling. The work reported on here deals first with the techniques necessary for the translation, thus constructing a static view of an ER-model in an abstract setting of what might be called logic without variables. We then undertake a detailed analysis of the insertion and deletion operations for an ER-model represented in terms of the relation calculus. [Copyright &y& Elsevier]

The paradigm of algebraic constraint-based reasoning, embodied in the notion of a qualitative calculus, is studied within two alternative frameworks. One framework defines a qualitative calculus as "a non-associative relation algebra (NA) with a qualitative representation", the other as "an algebra generated by jointly exhaustive and pairwise disjoint (JEPD) relations". These frameworks provide complementary perspectives: the first is intensional (axiom-based), whereas the second one is extensional (based on semantic structures). However, each definition admits calculi that lie beyond the scope of the other. Thus, a qualitatively representable NA may be incomplete or non-atomic, whereas an algebra generated by JEPD relations may have non-involutive converse and no identity element. The divergence of definitions creates a confusion around the notion of a qualitative calculus and makes the "what" question posed by Ligozat and Renz actual once again. Here we define the relation-type qualitative calculus unifying the intensional and extensional approaches. By introducing the notions of weak identity, inference completeness and Q-homomorphism, we give equivalent definitions of qualitative calculi both intensionally and extensionally. We show that "algebras generated by JEPD relations" and "qualitatively representable NAs" are embedded into the class of relation-type qualitative algebras. [ABSTRACT FROM AUTHOR]