Random Finite Structures

[406809] Lynch本研究的中心主题是分析随机有限结构的逻辑可定义性质。将研究的有限结构的种类出现在关系数据库理论、描述复杂性理论、操作系统和算法分析中。检查随机结构有两个动机。首先，许多形式语言的逻辑可定义属性在随机有限结构上具有非常规则的行为。例如，随着随机结构的基数增加，语言中的每个句子可能具有收敛到极限的概率。通常，语言的可定义属性对应于某些类型的计算问题。然后，可以利用正则性条件来表明某些问题不属于该类：如果一个问题不满足正则性条件，那么它就不属于该类。另一个动机是，许多计算过程，甚至是确定性过程，都是不可预测的，因为它们的输入是不可预测的。然后，为了估计事件的可能性或频率，概率分析是必要的。要研究的事件包括数据库查询的满足和多程序系统中的死锁。这两者在某些形式语言中都是可定义的。

9406809 Lynch The central theme of the proposed research is the analysis of logically definable properties of random finite structures. The kinds of finite structures that will be investigated occur in the theory of relational databases, descriptive complexity theory, operating systems, and the analysis of algorithms. There are two motivations for examining random structures. First, the logically definable properties of many formal languages have a very regular behavior on random finite structures. For example, every sentence in the language may have probability that converges to a limit, as the cardinality of the random structure increases. Often, the definable properties of a language correspond to some class of computational problems. Then the regularity condition can be exploited to show that some problems are not in the class: if a problem does not satisfy the regularity condition, then it does not belong to the class. The other motivation is that many computational processes, even deterministic ones, are unpredictable because their inputs are unpredictable. Then in order to estimate the likelihood or frequency of events, probabilistic analysis is necessary. The events be investigated include satisfaction of database queries and deadlock in multiprogramming systems. Both of these are definable in certain formal languages.