Search

In computer science, scenarios with interacting agents are often developed using modal logic. We show how to interpret modal logic of knowledge in relation algebra. This allows the use of the RelView tool for the purpose of investigating finite models and for visualizing certain properties. Our approach is illustrated with the well-known ‘muddy children' puzzle using modal logic of knowledge. We also sketch how to treat other non-classical logics in this way. In particular, we explore our approach for computational tree logic and illustrate it with the ‘mutual exclusion' example. [ABSTRACT FROM AUTHOR]

This paper concerns an interdisciplinary approach to coalition formation. We apply the MacBeth software, relational algebra, the RelView tool, graph theory, bargaining theory, social choice theory, and consensus reaching to a model of coalition formation. A feasible government is a pair consisting of a coalition of parties and a policy supported by this coalition. A feasible government is stable if it is not dominated by any other feasible government. Each party evaluates each government with respect to certain criteria. MacBeth helps to quantify the importance of the criteria and the attractiveness and repulsiveness of governments to parties with respect to the given criteria. Feasibility, dominance, and stability are formulated in relation-algebraic terms. The RelView tool is used to compute the dominance relation and the set of all stable governments. In case there is no stable government, i.e., in case the dominance relation is cyclic, we apply graph-theoretical techniques for breaking the cycles. If the solution is not unique, we select the final government by applying bargaining or appropriate social choice rules. We describe how a coalition may form a government by reaching consensus about a policy. Keywords: stable government, MacBeth, relational algebra, RelView, graph theory, bargaining, social choice rule, consensus. [ABSTRACT FROM AUTHOR]

Randomized search heuristics, among them evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to hard problems in combinatorial optimization to get near-optimal solutions. We present a new approach implementing simple parallel evolutionary algorithms by relational methods. Populations are represented as relations which are implicitly encoded by (reduced, ordered) binary decision diagrams. Thereby, the creation and evaluation is done in parallel, which increases efficiency considerably. [ABSTRACT FROM AUTHOR]

We present a method for specifying and implementing algorithms for Boolean logic problems. It is formally grounded in relational algebra. Specifications are written in first-order set theory and then transformed systematically into relation-algebraic forms which can be executed directly in RelView, a computer system for the manipulation of relations and relational programming. Our method yields programs that are correct by construction. It is illustrated by some examples. [ABSTRACT FROM AUTHOR]

We model groups as relational systems and develop relation-algebraic specifications for direct products of groups, quotient groups, and the enumeration of all subgroups and normal subgroups. The latter two specifications immediately lead to specifications of the lattices of subgroups and normal subgroups, respectively. All specifications are algorithmic and can directly be translated into the language of the computer system RelView. Hence, the system can be used for constructing groups and for computing and visualizing their lattices of subgroups and normal subgroups. This is demonstrated by some examples. [ABSTRACT FROM AUTHOR]

We present an OBDD-based Computer Algebra system for relational algebra, called RelView. After a short introduction to the OBDD-implementation of relations and the system, we exhibit its application by presenting two typical examples. [ABSTRACT FROM AUTHOR]

We use Tarski's relational algebra to derive a series of algorithms for computing spanning trees of undirected graphs, including a variant of Prim's minimum spanning tree algorithm. [ABSTRACT FROM AUTHOR]