CSL ’88: 2nd Workshop on Computer Science Logic Duisburg, FRG, October 3–7, 1988 Proceedings

Klaus Ambos-Spies, Jürgen Kämper (auth.), Egon Börger, Hans Kleine Büning, Michael M. Richter (eds.)354051659X, 9783540516590

This volume contains the papers which were presented at the second workshop “Computer Science Logic” held in Duisburg, FRG, October 3-7, 1988. These proceedings cover a wide range of topics both from theoretical and applied areas of computer science. More specifically, the papers deal with problems arising at the border of logic and computer science: e.g. in complexity, data base theory, logic programming, artificial intelligence, and concurrency. The volume should be of interest to all logicians and computer scientists working in the above fields.

---

Table of contents :
On disjunctive self-reducibility….Pages 1-13
The knowledge representation language L LILOG ….Pages 14-51
Completeness with respect to interpretations in deterministic and nondeterministic polynomial time….Pages 52-62
A temporal logic approach to specify and to prove properties of finite state concurrent systems….Pages 63-79
A comparison of the resolution calculus and the connection method, and a new calculus generalizing both methods….Pages 80-98
Characterizing complexity classes by general recursive definitions in higher types….Pages 99-117
Size of models versus length of computations….Pages 118-137
Boolean circuit complexity of algebraic interpolation problems….Pages 138-147
Loop detection in propositional Prolog programs….Pages 148-165
Numberings of R 1 ∪F….Pages 166-186
Interval temporal logic and star-free expressions….Pages 187-198
An interpreter with lazy evaluation for Prolog with functions….Pages 199-225
On the complexity of the decision problem in propositional nonmonotonic logic….Pages 226-239
Gentzen-Systems for propositional temporal logics….Pages 240-253
Predicate inequalities as a basis for automated termination proofs for Prolog programs….Pages 254-271
On the existence of fair schedulers….Pages 272-287
Using finite-linear temporal logic for specifying database dynamics….Pages 288-300
Is average superlinear speedup possible?….Pages 301-312
Enforcement of integrity constraints in a semantic data model….Pages 313-328
Delete operations and Horn formulas….Pages 329-343
Integration of descriptive and procedural language constructs….Pages 344-356
Normal forms and the complexity of computations of logic programs….Pages 357-371
A remark on minimal polynomials of Boolean functions….Pages 372-383
On the emptiness problem of tree automata and completeness of modal logics of programs….Pages 384-399