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.