Problems in Finite Model Theory

点击翻译按钮获取中文摘要

This project consists of three parts: asymptotic probabilities of sentences about finite models, random resource allocation graphs, and definability of sets of finite models. In the first part, the general type of problem is: given a class of finite models and a sentence appropriate to them, estimate the probability that the sentence holds, for large models in the class. Also, for randomly evolving finite models, determine the expected waiting time until the sentence holds. Various classes of models and probability distributions will be investigated. In the second part, a resource allocation graph is a structure that models the state of a multiprogramming computer system. As processes request and release resources, the resource allocation graph evolves stochastically. The expectations of the following random variables will be studied: the waiting time until deadlock, the number of unblocked processes, and the size of the first cycle when deadlock occurs. The third part is an investigation of whether certain sets of finite models cannot be defined by monadic existential sentences with at most one alternation in the first-order part of their prenex normal form prefix. This would have implications for nonlinear lower time bounds.