## Logic and Random Structures: DIMACS Workshop, November 5-7, 1995This 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 |

### Other editions - View all

Logic and Random Structures: DIMACS Workshop, November 5-7, 1995 DIMACS (Group) Limited preview - 1997 |

### Common terms and phrases

Abelian groups admissible class algebras asymptotic probability binary relation Boolean function bounded cardinality circuit complete system Compton congruence construction convergence law COROLLARY cumulative measure defined definition denote DIMACS directly join directly representable variety disjoint union Duplicator edge probability Editors element equivalent exists fc-extendible fc-universal finite structures first-order 0-1 law first-order limit laws first-order logic first-order sentence fixed formula global graph G holds indecomposables induction input integer isomorphism join irreducible language Mathematical modular lattice monadic second order multiplicative natural number nonconvergence nonstandard normal subgroup order sentence order theory Ore's Theorem pair partial structure partition pebble polynomial predicate proof of Theorem prove quantifier random graphs recursive relation restriction Saharon Shelah satisfies semigeneric sequence Shelah spectrally determined Spoiler standard subgroup of G sublemma subset sufficiently large Suppose Switching Lemma Sylow subgroup symbol Theorem 1.1 theory tp(x tuple variables vertex vertices