CSL '87

1. Front Matter

   PDF

2. Diagonalizing over deterministic polynomial time

   • Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig

   Pages 1-16

3. Resolution with feature unification

   • K. H. Bläsius, U. Hedtstück

   Pages 17-26

4. Surjectivity for finite sets of combinators by weak reduction

   • Corrado Böhm, Adolfo Piperno

   Pages 27-43

5. Proving finite satisfiability of deductive databases

   • François Bry, Rainer Manthey

   Pages 44-55

6. Is setl a suitable language for parallel programming — a theoretical approach

   • Elias Dahlhaus

   Pages 56-63

7. Loose diagrams, semigroupoids, categories, groupoids and iteration

   • G. Germano, S. Mazzanti

   Pages 64-80

8. Algebraic operational semantics and modula-2

   • Yuri Gurevich, James M. Morris

   Pages 81-101

9. Program verification using dynamic logic

   • M. Heisel, W. Reif, W. Stephan

   Pages 102-117

10. Induction in the elementary theory of types and names

    • Gerhard Jäger

    Pages 118-128

11. On the computational complexity of quantified Horn clauses

    • Marek Karpinski, Hans Kleine Büning, Peter H. Schmitt

    Pages 129-137

12. The conjunctive complexity of quadratic boolean functions

    • Katja Lenz, Ingo Wegener

    Pages 138-150

13. On type inference for object-oriented programming languages

    • Hans Leiß

    Pages 151-172

14. Optimization aspects of logical formulas

    • Ulrich Löwen

    Pages 173-187

15. Logic of approximation reasoning

    • Helena Rasiowa

    Pages 188-210

16. Deciding the path- and word-fair equivalence problem

    • Ralf Rehrmann, Lutz Priese

    Pages 211-222

17. Learning by teams from examples with errors

    • Reinhard Rinn, Britta Schinzel

    Pages 223-234

18. A survey of rewrite systems

    • P. H. Schmitt

    Pages 235-262

19. Interfacing a logic machine

    • Wolfgang Schönfeld

    Pages 263-272

20. Complexity cores and hard-to-prove formulas

    • Uwe Schöning

    Pages 273-280

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.

• Boolean function
• Computer
• Erfüllbarkeitsproblem der Aussagenlogik
• Resolution
• algorithm
• algorithms
• complexity
• logic
• mathematical logic
• optimization
• programming
• programming language
• proof theory
• semantics
• verification

Policies and ethics