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.
Author(s): Felice Cardone (auth.), Daniel Leivant (eds.)
Series: Lecture Notes in Computer Science 960
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1995
Language: English
Pages: 520
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Mathematical Logic and Formal Languages; Mathematical Logic and Foundations
Strict finitism and feasibility....Pages 1-21
Logical omniscience....Pages 22-29
On feasible numbers....Pages 30-51
Program extraction from classical proofs....Pages 52-76
Computation models and function algebras....Pages 77-97
Expressing computational complexity in constructive type theory....Pages 98-130
Light linear logic....Pages 131-144
Intrinsic theories and computational complexity....Pages 145-176
On Herbrand's theorem....Pages 177-194
Frege proof system and TNC ° ....Pages 195-209
Characterizing parallel time by type 2 recursions with polynomial output length....Pages 210-220
Type 2 polynomial hierarchies....Pages 221-252
The hierarchy of terminating recursive programs over N....Pages 253-268
Feasibly categorical models....Pages 269-280
Metafinite model theory....Pages 281-299
Automatic presentations of structures....Pages 300-312
A restricted second order logic for finite structures....Pages 313-366
Comparing the power of monadic NP games....Pages 367-392
Linear constraint query languages expressive power and complexity....Pages 393-413
A constant-space sequential model of computation for first-order logic....Pages 414-425
Logics capturing relativized complexity classes uniformly....Pages 426-446
Preservation theorems in finite model theory....Pages 447-462
A query language for NC (extended abstract)....Pages 463-479
....Pages 480-502
