Computer Science Logic: 4th Workshop, CSL ’90 Heidelberg, Germany, October 1–5, 1990 Proceedings

Stefan Arnborg, Andrzej Proskurowski, Detlef Seese (auth.), Egon Börger, Hans Kleine Büning, Michael M. Richter, Wolfgang Schönfeld (eds.)3540544879, 9783540544876

The workshop Computer Science Logic ’90 was held at the Max-Planck-Haus in Heidelberg, Germany, October 1-5, 1990. It was the fourth in a series of worskhops, following CSL ’89 at the University of Kaiserslautern (see LNCS 440), CSL ’88 at the University of Duisberg (see LNCS 385), and CSL ’87 at the University of Karlsruhe (see LNCS 329). This volume contains 24 papers, chosen by means of a review procedure from the 35 papers presented at the workshop, some of which were invited and some selected from a total of 89 submissions. The papers cover a wide range of topics arising from the applications of logic to computer science.

---

Table of contents :
Monadic second order logic, tree automata and forbidden minors….Pages 1-16
On the reduction theory for average case complexity….Pages 17-30
From prolog algebras towards WAM-A mathematical study of implementation….Pages 31-66
A formal operational semantics for languages of type Prolog III….Pages 67-79
Efficiency considerations on goal-directed forward chaining for logic programs….Pages 80-94
Decision problems for tarski and presburger arithmetics extended with sets….Pages 95-109
A fast garbage collection algorithm for WAM — based PROLOG….Pages 110-127
A resolution variant deciding some classes of clause sets….Pages 128-144
Subclasses of quantified boolean formulas….Pages 145-155
Algorithmic proof with diminishing resources part 1….Pages 156-173
Cutting plane versus frege proof systems….Pages 174-194
RAM with compact memory: a realistic and robust model of computation….Pages 195-233
Randomness and turing reducibility restraints….Pages 234-247
Towards an efficient tableau proof procedure for multiple-valued logics….Pages 248-260
Interactive proof systems: Provers, rounds, and error bounds….Pages 261-273
Logics for belief dependence….Pages 274-288
A generalization of stability and its application to circumscription of positive introspective knowledge….Pages 289-299
The complexity of adaptive error-correcting codes….Pages 300-307
Ramsey’s theorem in bounded arithmetic….Pages 308-317
Nontrivial lower bounds for some NP-problems on directed graphs….Pages 318-339
Expansions and models of autoepistemic theories….Pages 340-353
On the existence of fixpoints in moore’s autoepistemic logic and the non-monotonic logic of McDermott and Doyle….Pages 354-365
On the tracking of loops in automated deductions….Pages 366-388
The gap-language-technique revisited….Pages 389-399