Logic and Random Structures: DIMACS Workshop, November 5-7, 1995

Front Cover
Ravi Bopu Boppana, James F. Lynch
American Mathematical Soc., Jan 1, 1997 - Computers - 130 pages
This volume contains selected papers from the DIMACS Workshop on Logic an Random Structures held in November 1995. The workshop was a major event of the DIMACS Special Year on Logic and Algorithms. The central theme was the relationship between logic and probabilistic techniques in the study of finite structures. In the last several years, this subject has developed into a very active area of mathematical logic with important connections to computer science. The DIMACS workshop was the first of its kind devoted to logic and random structures. Recent work of leaders in the field is contained in the volume, as well as new theoretical developments and applications to computer science.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Smoothness laws for random ordered graphs
15
Spectrally determined firstorder limit laws
33
The asymptotic behavior of L1 on sparse random graphs
53
Monadic second order probabilities in algebra Directly representable
79
Approximating the structures accepted by a constant depth circuit
109
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information