Computer Science Logic

6th Workshop, CSL'92, San Miniato, Italy, September 28 - October 2, 1992. Selected Papers
1993
ISBN: 978-3-540-56992-3
Verlag: Springer Berlin Heidelberg

Buch, Englisch, Band 702, 439 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1410 g

Reihe: Lecture Notes in Computer Science

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.

Zielgruppe

Research

Autoren/Hrsg.

Börger, Egon

Jäger, Gerhard

Richter, Michael M.

Kleine Büning, Hans

Martini, Simone

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Algebra Elementare Algebra
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
• Mathematik | Informatik Mathematik Mathematik Allgemein Mathematische Logik
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten

Inhaltsverzeichnis

A universal Turing machine.- Recursive inseparability in linear logic.- The basic logic of proofs.- Algorithmic structuring of cut-free proofs.- Optimization problems: 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 II: Polynomial-time oracle machines.- On asymptotic probabilities of monadic second order properties.