Search

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: Problem statements often resort to superlatives such as in e.g. “… the smallest such number”, “… the best approximation”, “… the longest such list” which lead to specifications made of two parts: one defining a broad class of solutions (the easy part) and the other requesting one particular such solution, optimal in some sense (the hard part). This article introduces a binary relational combinator which mirrors this linguistic structure and exploits its potential for calculating programs by optimization. This applies in particular to specifications written in the form of Galois connections, in which one of the adjoints delivers the optimal solution. The framework encompasses re-factoring of results previously developed by Bird and de Moor for greedy and dynamic programming, in a way which makes them less technically involved and therefore easier to understand and play with. [Copyright &y& Elsevier]

Abstract: That matrices of relations also obey the rules of relation algebra is well known. When the powerset ordering is considered, partialities may be conceived as lattice-continuous mappings — corresponding to existential images which are often studied independently. A partiality is suited to describe progress of yet partial information or availability. This has already been presented in Schmidt (2006) . Matrices of partialities will considerably improve the possibility to study non-strictness, streams, partial evaluation, and net properties in a compact relation-algebraic form. They seem, however, to lead inevitably to some borderline cases as the Boolean lattice 0 and row-less matrices. It will be shown how these can be fruitfully applied concerning constructions with temporarily non-connected relation algebras. [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: The family of domain algebras provide an elegant formal system for automated reasoning about programme verification. Their primary models are algebras of relations, viz. representable domain algebras. We prove that, even for the minimal signature consisting of the domain and composition operations, the class of representable domain algebras is not finitely axiomatizable. Then we show similar results for extended similarity types of domain algebras. [ABSTRACT FROM AUTHOR]

Abstract: We elaborate our relational model of non-strict, imperative computations. The theory is extended to support infinite data structures. To facilitate their use in programs, we extend the programming language by concepts such as procedures, parameters, partial application, algebraic data types, pattern matching and list comprehensions. For each concept, we provide a relational semantics. Abstraction is further improved by programming patterns such as fold, unfold and divide-and-conquer. To support program reasoning, we prove laws such as fold–map fusion, otherwise known from functional programming languages. We give examples to show the use of our concepts in programs. [ABSTRACT FROM AUTHOR]

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: Restating a unification problem as a single relational substitution instead of as multiple functional substitutions (or terms), a solution becomes a “determiniser” arrow and allows formalisation in the context of locally ordered categories with domain. This relies on the determinacy concept of “characterisation by domain” introduced by Desharnais and Möller for Kleene algebras with domain; this is here applied in the weakest possible setting. We show how “most general determinisers” can be seen as generalisation of quotient projections of partial equivalence relations, and show a characterisation that manages to avoid using converse or symmetry by employing restricted residuals instead. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we want to investigate three notions of the cardinality of relations in the context of allegories. Two of the three axiom systems are motivated on the existence of injective and surjective functions, respectively. Since those notions may differ we provide a third unifying definition of cardinality. In all cases we provide a canonical cardinality function and show that it is initial in the category of all cardinality functions over the given allegory. [ABSTRACT FROM AUTHOR]

Abstract: The language of our Boolean logic with relations is a Boolean language to which relation symbols have been added. Such a language turns out to be a useful tool for describing relational structures and algebraic structures. This paper introduces the concepts of Kripke semantics and Boolean semantics for our language. It addresses the traditional issues of decidability/complexity and axiomatization/completeness but it also defines the new concepts of weak canonicity and strong canonicity. [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: Finite maps or finite relations between infinite sets do not even form a category, since the necessary identities are not finite. We show relation-algebraic extensions of semigroupoids where the operations that would produce infinite results have been replaced with variants that preserve finiteness, but still satisfy useful algebraic laws. The resulting theories allow calculational reasoning in the relation-algebraic style with only minor sacrifices; our emphasis on generality even provides some concepts in theories where they had not been available before. The semigroupoid theories presented in this paper also can directly guide library interface design and thus be used for principled relation-algebraic programming; an example implementation in Haskell allows manipulating finite binary relations as data in a point-free relation-algebraic programming style that integrates naturally with the current Haskell collection types. This approach enables seamless integration of relation-algebraic formulations to provide elegant solutions of problems that, with different data organisation, are awkward to tackle. [Copyright &y& Elsevier]

Abstract: The relational product construction is often consider as an abstract version of cartesian products. The existence of those products is strongly connected with the representability of that category. In this paper we investigate a canonical weakening of the notion of a relational product. Unlike the strong version, any (small) category of relations can be embedded into a suitable category providing all weak relational products. Furthermore, we provide several examples, and we study the categorical properties of the new construction. [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]

Abstract: The importance of relational methods in temporal and spatial reasoning has been widely recognised in the last two decades. A quite large part of contemporary spatial reasoning is concerned with the research of relation algebras generated by the “part of” and “connection” relations in various domains. This paper is devoted to the study of one particular relation algebra appeared in the literature, viz. the complemented disk algebra. This algebra was first described by Düntsch [I. Düntsch, A tutorial on relation algebras and their application in spatial reasoning, Given at COSIT, August 1999, Available from: ] and then, Li et al. [Y. Li, S. Li, M. Ying, Relational reasoning in the Region Connection Calculus, Preprint, 2003, Available from: http://arxiv.org/abs/cs/0505041] showed that closed disks and their complements provides a representation. This set of regions is rather restrictive and, thus, of limited practical values. This paper will provide a general method for generating representations of this algebra in the framework of Region Connection Calculus. In particular, connected regions bounded by Jordan curves and their complements is also such a representation. [Copyright &y& Elsevier]