CSL ’87: 1st Workshop on Computer Science Logic Karlsruhe, FRG, October 12–16, 1987 Proceedings

Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig (auth.), Egon Börger, Hans Kleine Büning, Michael M. Richter (eds.)3540502416, 9783540502418

This volume contains the papers which were presented to the workshop “Computer-Science Logic” held in Karlsruhe on October 12-16, 1987. Traditionally Logic, or more specifically, Mathematical Logic splits into several subareas: Set Theory, Proof Theory, Recursion Theory, and Model Theory. In addition there is what sometimes is called Philosophical Logic which deals with topics like nonclassical logics and which for historical reasons has been developed mainly at philosphical departments rather than at mathematics institutions. Today Computer Science challenges Logic in a new way. The theoretical analysis of problems in Computer Science for intrinsic reasons has pointed back to Logic. A broad class of questions became visible which is of a basically logical nature. These questions are often related to some of the traditional disciplines of Logic but normally without being covered adequately by any of them. The novel and unifying aspect of this new branch of Logic is the algorithmic point of view which is based on experiences people had with computers. The aim of the “Computer-Science Logic” workshop and of this volume is to represent the richness of research activities in this field in the German-speaking countries and to point to their underlying general logical principles.

---

Table of contents :
Diagonalizing over deterministic polynomial time….Pages 1-16
Resolution with feature unification….Pages 17-26
Surjectivity for finite sets of combinators by weak reduction….Pages 27-43
Proving finite satisfiability of deductive databases….Pages 44-55
Is setl a suitable language for parallel programming — a theoretical approach….Pages 56-63
Loose diagrams, semigroupoids, categories, groupoids and iteration….Pages 64-80
Algebraic operational semantics and modula-2….Pages 81-101
Program verification using dynamic logic….Pages 102-117
Induction in the elementary theory of types and names….Pages 118-128
On the computational complexity of quantified Horn clauses….Pages 129-137
The conjunctive complexity of quadratic boolean functions….Pages 138-150
On type inference for object-oriented programming languages….Pages 151-172
Optimization aspects of logical formulas….Pages 173-187
Logic of approximation reasoning….Pages 188-210
Deciding the path- and word-fair equivalence problem….Pages 211-222
Learning by teams from examples with errors….Pages 223-234
A survey of rewrite systems….Pages 235-262
Interfacing a logic machine….Pages 263-272
Complexity cores and hard-to-prove formulas….Pages 273-280
On the average case complexity of backtracking for the exact-satisfiability problem….Pages 281-288
On functions computable in nondeterministic polynomial time: Some characterizations….Pages 289-303
Developing logic programs: Computing through normalizing….Pages 304-321
Model theory of deductive databases….Pages 322-334
Algorithms for propositional updates….Pages 335-346