CSL ’89: 3rd Workshop on Computer Science Logic Kaiserslautern, FRG, October 2–6, 1989 Proceedings

Klaus Ambos-Spies, Dongping Yang (auth.), Egon Börger, Hans Kleine Büning, Michael M. Richter (eds.)3540527532, 9783540527534

This volume contains the revised versions of 28 papers presented at the third workshop on Computer Science Logic held in Kaiserslautern, FRG, October 2-6, 1989. 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 intelligece, and temporal logic. The volume should be of interest to all logicians and computer scientists working in the above field.

---

Table of contents :
Honest polynomial-time degrees of elementary recursive sets….Pages 1-15
On the verification of modules….Pages 16-35
A logical operational semantics of full Prolog….Pages 36-64
Set-theoretic reductions of Hilbert’s tenth problem….Pages 65-75
The complexity of subtheories of the existential linear theory of reals….Pages 76-89
On test classes for universal theories….Pages 90-97
Generalizing allowedness while retaining completeness of SLDNF-resolution….Pages 98-115
Effectively given information systems and domains….Pages 116-142
Davis-Putnam resolution versus unrestricted resolution….Pages 143-162
On logical descriptions of some concepts in structural complexity theory….Pages 163-175
Algebraic operational semantics and Occam….Pages 176-192
Propositional provability and models of weak arithmetic….Pages 193-210
Polymorphic recursion and semi-unification….Pages 211-224
Deciding Horn classes by hyperresolution….Pages 225-241
Ω-branching programs of bounded width….Pages 242-253
A predicate calculus with control of derivations….Pages 254-266
Reducibility of monotone formulas to μ-formulas….Pages 267-270
New ways for developing proof theories for first-order multi modal logics….Pages 271-308
On the representation of data in lambda-calculus….Pages 309-321
A streamlined temporal completeness theorem….Pages 322-336
A concurrent branching time temporal logic….Pages 337-354
Semantic for abstract fairness using metric spaces….Pages 355-368
On the average time complexity of set partitioning….Pages 369-381
A direct proof for the completeness of SLD-resolution….Pages 382-383
A quantifier-free completion of logic programs….Pages 384-395
Stratification of definite clause programs and of general logic programs….Pages 396-408
The semantics of disjunctive deductive databases….Pages 409-421
Sequential representation of primitive recursive functions, and complexity classes….Pages 422-437