Authors		Title	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 Gunther.Schmidt@Unibw.DE		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.