Computer Science Logic

1. Front Matter

   PDF

2. A universal Turing machine

   • Stål Aanderaa

   Pages 1-4

3. Recursive inseparability in linear logic

   • Stål Aanderaa, Herman Ruge Jervell

   Pages 5-13

4. The basic logic of proofs

   • Sergei Artëmov, Tyko Straßen

   Pages 14-28

5. Algorithmic structuring of cut-free proofs

   • Matthias Baaz, Richard Zach

   Pages 29-42

6. Optimization problems: Expressibility, approximation properties and expected asymptotic growth of optimal solutions

   • Thomas Behrendt, Kevin Compton, Erich Grädel

   Pages 43-60

7. Linear λ-calculus and categorical models revisited

   • Nick Benton, Gavin Bierman, Valeria de Paiva, Martin Hyland

   Pages 61-84

8. A self-interpreter of lambda calculus having a normal form

   • Alessandro Berarducci, Corrado Böhm

   Pages 85-99

9. An “Ehrenfeucht-Fraïssé game” for fixpoint logic and stratified fixpoint logic

   • Uwe Bosse

   Pages 100-114

10. The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness

    • Nadia Creignou

    Pages 115-133

11. Model building by resolution

    • Christian G. Fermüller, Alexander Leitsch

    Pages 134-148

12. Comparative transition system semantics

    • Tim Fernando

    Pages 149-166

13. Reasoning with higher order partial functions

    • A. Gavilanes-Franco, F. Lucio-Carrasco, M. Rodríguez-Artalejo

    Pages 167-181

14. Communicating evolving algebras

    • Paola Glavan, Dean Rosenzweig

    Pages 182-215

15. On the completeness of narrowing as the operational semantics of functional logic programming

    • Juan Carlos González-Moreno, María Teresa Hortalá-González, Mario Rodríguez-Artalejo

    Pages 216-230

16. Inductive definability with counting on finite structures

    • Erich Grädel, Martin Otto

    Pages 231-247

17. Linear time algorithms and NP-complete problems

    • Etienne Grandjean

    Pages 248-273

18. The semantics of the C programming language

    • Yuri Gurevich, James K. Huggins

    Pages 274-308

19. A theory of classes for a functional language with effects

    • Furio Honsell, Ian A. Mason, Scott Smith, Carolyn Talcott

    Pages 309-326

20. Logical definability of NP-optimisation problems with monadic auxiliary predicates

    • Clemens Lautemann

    Pages 327-339

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.

• Resolution
• computer
• computer science
• lambda calculus
• logic
• optimization
• programming
• semantics
• algorithm analysis and problem complexity

Policies and ethics