Computer Science Logic: 6th Workshop, CSL ’92 San Miniato, Italy, September 28 – October 2, 1992 Selected Papers

Stål Aanderaa (auth.), E. Börger, G. Jäger, H. Kleine Büning, S. Martini, M. M. Richter (eds.)3540569928, 9783540569923

This volume presents the proceedings of the Computer Science Logic Workshop CSL ’92, held in Pisa, Italy, in September/October 1992. CSL ’92 was the sixth of the series and the first one held as Annual Conference of the European Association for Computer Science Logic (EACSL). Full versions of the workshop contributions were collected after their presentation and reviewed. On the basis of 58 reviews, 26 papers were selected for publication, and appear here in revised final form. Topics covered in the volume include: Turing machines, linear logic, logic of proofs, optimization problems, lambda calculus, fixpoint logic, NP-completeness, resolution, transition system semantics, higher order partial functions, evolving algebras, functional logic programming, inductive definability, semantics of C, classes for a functional language, NP-optimization problems, theory of types and names, sconing and relators, 3-satisfiability, Kleene’s slash, negation-complete logic programs, polynomial-time oracle machines, and monadic second-order properties.

---

Table of contents :
A universal Turing machine….Pages 1-4
Recursive inseparability in linear logic….Pages 5-13
The basic logic of proofs….Pages 14-28
Algorithmic structuring of cut-free proofs….Pages 29-42
Optimization problems: Expressibility, approximation properties and expected asymptotic growth of optimal solutions….Pages 43-60
Linear λ-calculus and categorical models revisited….Pages 61-84
A self-interpreter of lambda calculus having a normal form….Pages 85-99
An “Ehrenfeucht-Fraïssé game” for fixpoint logic and stratified fixpoint logic….Pages 100-114
The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness….Pages 115-133
Model building by resolution….Pages 134-148
Comparative transition system semantics….Pages 149-166
Reasoning with higher order partial functions….Pages 167-181
Communicating evolving algebras….Pages 182-215
On the completeness of narrowing as the operational semantics of functional logic programming….Pages 216-230
Inductive definability with counting on finite structures….Pages 231-247
Linear time algorithms and NP-complete problems….Pages 248-273
The semantics of the C programming language….Pages 274-308
A theory of classes for a functional language with effects….Pages 309-326
Logical definability of NP-optimisation problems with monadic auxiliary predicates….Pages 327-339
Universes in the theories of types and names….Pages 340-351
Notes on sconing and relators….Pages 352-378
Solving 3-satisfiability in less than 1, 579 n steps….Pages 379-394
Kleene’s slash and existence of values of open terms in type theory….Pages 395-402
Negation-complete logic programs….Pages 403-409
Logical characterization of bounded query classes II: Polynomial-time oracle machines….Pages 410-424
On asymptotic probabilities of monadic second order properties….Pages 425-439