Title Logic and computational complexity : international workshop, LCC '94, Indianapolis, IN, USA, October 13-16, 1994 : selected papers / Daniel Leivant (ed.)

Published Berlin ; New York : Springer, ©1995

Click on the following:
Springer eBooks

Copies

Description 1 online resource (viii, 514 pages) : illustrations Series Lecture notes in computer science ; 960 Lecture notes in computer science ; 960. Contents Strict finitism and feasibility / Felice Cardone -- Logical omniscience / Rohit Parikh -- On feasible numbers / Vladimir Yu. Sazonov -- On parallel hierarchies and R[i over k] / Stephen Bloch -- Program extraction from classical proofs / Ulrich Berger and Helmut Schwichtenberg -- Computational models and function algebras / Peter Clote -- Expressing computational complexity in constructive type theory / Robert L. Constable -- Light linear logic / Jean-Yves Girard -- Intrinsic theories and computational complexity / Daniel Leivant -- On Herbrand's theorem / Samuel R. Buss -- Some consequences of cryptographical conjectures for S1/2 and EF / Jan Krajíček and Pavel Pudlák -- Frege proof system and TNC[superscript]̊ / Gaisi Takeuti -- Characterizing parallel time by type 2 recursions with polynomial output length / Stephen J. Bellantoni -- Type 2 polynomial hierarchies / Anil Seth -- The hierarchy of terminating recursive programs over N / Stanley S. Wainer -- Feasibly categorical models / Douglas Cenzer and Jeffrey B. Remmel -- Metafinite model theory / Erich Grädel and Yuri Gurevich -- Automatic presentations of structures / Bakhadyr Khoussainov and Anil Nerode -- A restricted second order logic for finite structures / Anuj Dawar -- Comparing the power of monadic NP games / Ronald Fagin -- Linear constraint query languages : expressive power and complexity / Stéphane Grumbach, Jianwen Su, and Christophe Tollu -- A constant-space sequential model of computation for first-order logic / Steven Lindell -- Logics capturing relativized complexity classes uniformly / J.A. Makowsky and Y.B. Pnueli -- Preservations theorems in finite model theory / Eric Rosen and Scott Weinstein -- A query language for NC / Dan Suciu and Val Breazu-Tannen Summary This book contains revised versions of papers invited for presentation at the International Workshop on Logic and Computational Complexity, LCC '94, held in Indianapolis, IN in October 1994. The synergy between logic and computational complexity has gained importance and vigor in recent years, cutting across many areas. The 25 revised full papers in this book contributed by internationally outstanding researchers document the state-of-the-art in this interdisciplinary field of growing interest; they are presented in sections on foundational issues, applicative and proof-theoretic complexity, complexity of proofs, computational complexity of functionals, complexity and model theory, and finite model theory Bibliography Includes bibliographical references Subject Logic, Symbolic and mathematical -- Congresses Computational complexity -- Congresses Computational complexity Logic, Symbolic and mathematical Berechnungskomplexität Berechnungstheorie Beweistheorie Datenverarbeitung Komplexität Komplexitätstheorie Logik Mathematische Logik Logica. Complexiteit. Logique symbolique et mathématique. Complexité de calcul (informatique) Indianapolis <Ind., 1994> Genre/Form Conference papers and proceedings Indianapolis (Ind., 1994) Form Electronic book Author Leivant, Daniel Maurice Raphaël ISBN 9783540447207 3540447202 3540601783 9783540601784

Other Titles LCC '94

  Permalink