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

by Egon Börger (editor)

A universal Turing machine.- Recursive inseparability in linear logic.- The basic logic of proofs.- Algorithmic structuring of cut-free proofs.- Optimization Expressibility, approximation properties and expected asymptotic growth of optimal solutions.- Linear ?-calculus and categorical models revisited.- A self-interpreter of lambda calculus having a normal form.- An "Ehrenfeucht-Fraïssé game" for fixpoint logic and stratified fixpoint logic.- The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness.- Model building by resolution.- Comparative transition system semantics.- Reasoning with higher order partial functions.- Communicating evolving algebras.- On the completeness of narrowing as the operational semantics of functional logic programming.- Inductive definability with counting on finite structures.- Linear time algorithms and NP-complete problems.- The semantics of the C programming language.- A theory of classes for a functional language with effects.- Logical definability of NP-optimisation problems with monadic auxiliary predicates.- Universes in the theories of types and names.- Notes on sconing and relators.- Solving 3-satisfiability in less than 1, 579n steps.- Kleene's slash and existence of values of open terms in type theory.- Negation-complete logic programs.- Logical characterization of bounded query classes Polynomial-time oracle machines.- On asymptotic probabilities of monadic second order properties.

456 pages, Paperback

Published March 12, 2014