Individual-based models are a relatively new approach to modelling dynamical systems of interacting entities, for example molecules in a biological cell. Although they are computationally expensive, they have the capability of modelling systems more realistically than traditional state-variable models. We give a formal definition of individual-based models, which includes state-variable models as a special case. We examine the questions of when state-variable models are sufficient for accurate modelling of a system, and when individual-based models are necessary. We define notions of abstraction and approximation, and give sufficient conditions that imply that an individual-based model can be approximated by a deterministic state-variable model. We also give negative results: examples of individual-based models that cannot be approximated by any state-variable model.

The degree sequence of an n -vertex graph is d 0 ,…, d n −1 , where each d i is the number of vertices of degree i in the graph. A random graph with degree sequence d 0 ,…, d n −1 is a randomly selected member of the set of graphs on {1,…, n } with that degree sequence, all choices being equally likely. Let λ 0 ,λ 1 ,… be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by λ 0 ,λ 1 ,… if, for every i and n , the members of the class of size n have λ i n + o(n) vertices of degree i . Our main result is a convergence law for random graphs with degree sequences approximated by some sequence λ 0 ,λ 1 ,…. With certain conditions on the sequence λ 0 ,λ 1 ,…, the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.

The degree sequence of an n-vertex graph is d/sub 0/, ..., d/sub n - 1/, where each d/sub i/ is the number of vertices of degree i in the graph. A random graph with degree sequence d/sub 0/, ..., d/sub n - 1/ is a randomly selected member of the set of graphs on {0, ..., n - 1} with that degree sequence, all choices being equally likely. Let /spl lambda/ /sub 0/, /spl lambda/ /sub 1/, ... be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by /spl lambda//sub 0/, /spl lambda//sub 1/, ... if, for every i and n, the members of the class of size n have /spl lambda//sub i/ n + o(n) vertices of degree i. Our main result is a convergence law for random graphs with degree sequences approximated by some sequence /spl lambda//sub 0/, /spl lambda//sub 1/, .... With certain conditions on the sequence /spl lambda//sub 0/, /spl lambda//sub 1/, ..., the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.

An estimation algorithm for a query is a probabilistic algorithm that computes an approximation for the size (number of tuples) of the query. One class of estimation algorithms uses a form of statistical sampling known as adaptive sampling. Several versions of adaptive sampling have been developed by other researchers. The original version has been surpassed in some ways by a newer version and a more specialized Monte-Carlo algorithm. An analysis of the cost of the original version is presented, and the different algorithms are compared. The analysis is used to derive an upper bound on the number of samples required by the original algorithm. Also, contrary to what seems to be a commonly held opinion, none of the algorithms is generally better than the other two. Which algorithm is superior depends on the query being estimated and the criteria that are being applied. Another question that is studied is which classes of logically definable queries have fast estimation algorithms. Evidence from descriptive complexity theory is provided that indicates not all such queries have fast estimation algorithms. However, it is shown that on classes of structures of bounded degree, all first-order queries have fast estimation algorithms.

Abstract Let be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n−1 satisfies certain simple conditions on its growth rate, then for every , the probability that σ holds for the random graph on n vertices converges. In fact, if p(n) = n−α, α > 1, then the probability is either smaller than for some d > 0, or it is asymptotic to cn−d for some c > 0, d ≥ 0. Results on the difficulty of computing the asymptotic probability are given.

Let L/sub /spl infin//spl omega///sup /spl omega// be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. Previous articles have shown that when p(n) is constant or p(n)=n/sup -/spl alpha// and /spl alpha/>1, then every sentence in L/sub /spl infin//spl omega///sup /spl omega// has probability that converges as n gets large; however, when p(n)=n/sup -/spl alpha// and /spl alpha/<1 is rational, then there are first-order sentences whose probability does not converge. This article completes the picture for L/sub /spl infin//spl omega///sup /spl omega// and random graphs with edge probability of the form n/sup -/spl alpha//. It is shown that if /spl alpha/ is irrational, then every sentence in L/sub /spl infin//spl omega///sup /spl omega// has probability that converges to 0 or 1. It is also shown that if /spl alpha/=1, then there are sentences an the deterministic transitive closure logic (and therefore in L/sub /spl infin//spl omega///sup /spl omega//), whose probability does not converge.

Resource allocation graphs are directed bipartite graphs satisfying certain constraints. The two partitions of the vertex set correspond to the processes and resources of a multi-programming computer system, and the edges indicate resource allocations and requests. When all the resources are distinguishable, existence of a cycle in such a graph is equivalent to deadlock in the system. The main results here are exact and asymptotic formulas for the number of resource allocation graphs and acyclic resource allocation graphs with m processes, n allocated resources, and q edges. If a uniform probability distribution is taken on such graphs, then the proportion of blocked processes, $( q - n )/m$, determines the asymptotic behavior of the probability of deadlock: If $( q - n )/m \to 0$, then the probability of deadlock is asymptotic to 0, and if $( q - n )/m \to \alpha > 0$, then the probability is asymptotic to a positive value. Similar formulas are also given in terms of m and n only.

The infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas, is considered. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n)1, then the probability is either smaller than 2 raised to the power-n/sup d/ for some d>0, or it is asymptotic to the cn/sup -d/ for some c>0, d>or=0. Results on the difficulty of computing the asymptotic probability are given.>

The author considers random graphs with edge probability beta n/sup - alpha /, where n is the number of vertices of the graph, beta >0 is fixed, and alpha =1 or alpha =(l+1)/l for some fixed positive integer l. It is proved that, for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit. Also, there is an effective procedure for generating the value of the limit in closed form.>

Abstract For every κ ∈ ω, there is an infinite set A κ ⊆ ω and a d (κ) ∈ ω such that for all Q 0 , Q 1 , ⊆ A κ where ∣ Q 0 ∣ = ∣ Q 1 ∣, or d (κ) < ∣ Q 0 ∣, Q 1 ∣ < ℵ 0 , the structures ‹ω, +, Q 0 › and ‹ω, +, Q 1 › are indistinguishable by first-order sentences of quantifier depth κ whose atomic formulas are of the form u = v, u + v = w , and Q ( u ), where u, v , and w are variables.