## Listing Graphs that Satisfy First Order Sentences

**Leslie Ann Goldberg**
*Abstract:* For every sentence Theta in the first order
language of graphs let *G*_{Theta}(\) denote the set of
*n*-vertex graphs that satisfy Theta and let *G*_{Theta}
denote the family of sets
{*G*_{Theta}(\infty),*G*_{Theta}(\null),...}. In this
work, we consider the following problem. Given a sentence Theta in
the first order language of graphs, design a fast algorithm that
takes as input a positive integer *n* and lists the members of
*G*_{Theta}(\). The criterion for ``fast'' that we use is
*polynomial delay*. We say that a listing algorithm for
*G*_{Theta} has polynomial delay if and only if there is a
polynomial such that when the algorithm is run with any input
*n* it executes at most *p(n)* machine instructions
before each successive member of *G*_{Theta}(\) is output. The
results that we obtain are related to a theorem which was proved
independently by Glebskii, Kogan, Liogon'kii, and Talanov and by
Fagin. They showed that for every sentence Theta in the first order
language of graphs the proportion of *n*-vertex graphs that
satisfy Theta is either o(1) or 1 - o(1). In the latter case we
call *G*_{Theta} an *almost sure first order graph
property*. In this paper we describe a general method that can
be used to obtain a polynomial delay listing algorithm for any
almost sure first order graph property.

*LFCS report ECS-LFCS-92-210*

Previous |

Index |

Next