Problems in Finite Model Theory

该项目由三部分组成：有限模型句子的渐近概率、随机资源分配图以及有限模型集的可定义性。 在第一部分中，问题的一般类型是：给定一类有限模型和适合它们的句子，对于该类中的大型模型，估计该句子成立的概率。 此外，对于随机演化的有限模型，确定句子成立之前的预期等待时间。 将研究各种类型的模型和概率分布。 在第二部分中，资源分配图是对多道程序计算机系统的状态进行建模的结构。 随着进程请求和释放资源，资源分配图随机变化。 将研究以下随机变量的期望：死锁之前的等待时间、未阻塞的进程数以及发生死锁时的第一个周期的大小。 第三部分是研究某些有限模型集是否不能由一元存在句子来定义，其 prenex 范式前缀的一阶部分最多有一次交替。 这将对非线性时间下限产生影响。

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.