VOLUME Thirty Three
TITLE: "Logic and Random Structures"
EDITORS: Ravi B. Boppana and James F. Lynch.

Ordering Information

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

• 1. Preface
• 2. Table of Contents

PREFACE

This volume contains selected papers from the DIMACS Workshop on Logic and Random Structures held November 5-7, 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.

TABLE OF CONTENTS

Foreword							 ix

Preface								 xi

Near model completeness and 0-1 laws
    John T. Baldwin						  1

Smoothness laws for random ordered graphs
    Ravi B. Boppana and Joel Spencer				 15


Spectrally determined first-order limit laws
    Stanley Burris						 33

The asymptotic behavior of Lkinfinity, omega  on sparse random graphs
    Monica McArthur						 53

k-universal finite graphs
    Eric Rosen, Saharon Shelah and Scott Weinstein		 65 

Monadic second order probabilities in algebra. Directly 
  representable varieties and groups
    Pawel M. Idziak and Jerzy Tyszkiewicz			 79

Approximating the structures accepted by a constant depth 
  circuit or satisfying a sentence--a nonstandard approach
    Alan R. Woods						109

Index of Volumes

DIMACS Homepage