Extensions of Logics Used in Computer Science and Their Decision Procedures

计算机科学中使用的逻辑的扩展及其决策过程

• 批准号: 8703807
• 负责人: Paul Schupp
• 金额: $ 5.98万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-07-15 至 1990-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8703807&HistoricalAwards=false
• 关键词: Extensions; Logics; Used; Computer; Science

Extensions of logics currently used in computer science are being investigated. Under particular consideration are extensions of temporal and dynamic logic which appear to be quite natural and to have considerable expressive power. A new model of alternating automata working on trees is being used that allows very simple and efficient decision procedures. In basic cases, proofs of decidability of the intended logics are being given that are simpler than the standard proofs for the unextended logics. Extensions of these methods are being attempted to questions involving protocols where knowledge should be taken into account for communicating systems. Also under consideration are some extremely strong dynamic logics with infinitary run quantifiers in which essentially any fairness condition can be expressed. The PIs propose to use tools they have developed in recent innovative work in formal language theory to investigate logics used in computer science. The theory program can properly devote funds toward the development and use of such methods in theoretical computer science. The proposed work ties together in a positive way the theory traditions of the U.S. and France.

目前在计算机科学中使用的逻辑的扩展正在被 研究了 特别要考虑的是， 和动态逻辑，看起来很自然， 相当大的表现力。 一种新的交替自动机模型 在树木上工作， 决策程序。 在基本情况下，证明的可判定性的 所给出的预期逻辑比标准逻辑更简单 非扩展逻辑的证明 这些方法的扩展正在 尝试涉及知识应该 考虑到通信系统。 也在考虑之中 是一些具有无穷游程量词的极强动态逻辑 其中基本上可以表达任何公平条件。 PI建议使用他们最近开发的创新工具， 研究形式语言理论，研究计算机中使用的逻辑 科学 理论计划可以适当地将资金投入到 这些方法在理论计算机科学中的发展和使用。 拟议的工作以积极的方式联系在一起的理论传统 美国和法国。