Random Finite Structures

随机有限结构

• 批准号: 9406809
• 负责人: James Lynch
• 金额: $ 8.81万
• 依托单位: Clarkson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-15 至 1998-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9406809&HistoricalAwards=false
• 关键词: Random; Finite; Structures

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.

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