Status, Abstract

Gunther Schmidt

Implication Structures

.pdf .bib

Presented at RelMiCS 8, Relational Methods in Computer Science

February 22-26, 2005, St. Catharines, Ontario, Canada

pages 227--237 of Participants Proceedings edited by Ivo Düntsch and Michael Winter, Brock University

Department of Computing Science
University of the Federal Armed Forces Munich
85577 Neubiberg, Germany

October 2004
This is a case study using the proposed relational multilevel reference language in order to deal with the interesting logical concept of implication structures, developed already in

Gunther Schmidt and Thomas Ströhlein
A Boolean Matrix Iteration in Timetable Construction
Linear Algebra and Its Applications 15 (1976) 27-51

In the course of these investigations, the timetable problem is introduced on a pointfree relational level by reworking the papers mentioned before, thus providing an important example of an implication structure.

An implication structure is given when a choice of a subset has to be made from a set of items where an item chosen may imply/forbid some others to be chosen. Also not choosing an item may enforce another one to be chosen. The problem is related to satisfiability. It is, thus, NP-complete, and will normally not admit an efficient algorithm. When studying the implication structure mentioned from the relation-algebraic side, this may result in theoretically sound heuristical approaches.