III-COR: Collaborative Research: Knowledge Compilation with Fast Response

III-COR：协作研究：快速响应的知识编译

• 批准号: 0712849
• 负责人: Neil Murray
• 金额: $ 23.43万
• 依托单位: SUNY at Albany
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0712849&HistoricalAwards=false
• 关键词: III; COR; Collaborative; Research; Knowledge

Abstract Project Title: Knowledge Compilation with Fast Response PIs: This project is concerned with the development, maintenance, and utilization of index structures -- reduced implicate tries (ri-tries) -- that answer logical queries of large databases. The primary goals of this project are further development of ri-tries, identification and classification of databases for which these tries will be effective, and development of computer systems that implement ri-tries. A reduced implicate trie is a data structure for storing a propositional database on a computer. Fast responses to queries are enabled by making it easy to determine consequences -- queries with yes answers -- of the database. Technically, once a database has been compiled into an ri-trie, the response time to any query is guaranteed to be linear in the size of the query, regardless of the size of the compiled database. This response time represents a trade-off between performance and space, since ri-tries may be large. A central focus of this project will be determining what types of databases lend themselves to ri-tries. This will be accomplished through experimentation and through theoretical developments. A prototype system that compiles logical formulas into ri-tries and a query processing module will be developed. Initially, the system will be designed for databases in conjunctive normal form; in the longer term, any formula from propositional logic will be acceptable input. The query processor will be designed to accept clauses as input, since a clause is the typical form for a query. Students at the University of New Haven and at SUNY at Albany will be active participants. Broader Impacts of the Proposed Activity The RUI component of this project will be extensive participation by undergraduates at the University of New Haven. Students will be introduced to the basic ideas of automated deduction and knowledge compilation and will work on the prototype system. The goal is to inspire students by engaging them in real research that contributes to real publications. The PI is committed to attracting talented young men and women into mathematics and computer science and to preparing them for graduate school. The University at Albany has a strong graduate program in computer science, and the PI at Albany is committed to preparing students for careers in research. Project Web Page: http://www.cs.albany.edu/~nvm/ritries/ Erik Rosenthal's Web Page: http://www.newhaven.edu/show.asp?durki=1623 Neil Murray's Web Page: http://www.cs.albany.edu/~nvm/

摘要项目标题：具有快速响应的知识汇编PI：该项目与索引结构的开发，维护和利用有关 - 减少牵引尝试（RI-Tries） - 回答大型数据库的逻辑查询。该项目的主要目标是进一步开发RI-Tries，这些尝试将是有效的数据库的识别和分类，以及实施RI-Tries的计算机系统的开发。减少的暗示TRIE是将命题数据库存储在计算机上的数据结构。通过使数据库中的后果（具有“是答案”的查询）易于确定，可以对查询进行快速响应。从技术上讲，一旦将数据库编译到RI-Trie中，无论编译数据库的大小如何，对任何查询的响应时间都可以在查询的大小上是线性的。此响应时间代表了性能与空间之间的权衡，因为RI-Tries可能很大。该项目的主要重点将是确定哪些类型的数据库为RI-Tries提供了。这将通过实验和理论发展来实现。将开发将逻辑公式编译成RI-Tries和查询处理模块的原型系统。最初，该系统将以连词正常形式为数据库设计。从长远来看，命题逻辑中的任何公式都将是可接受的输入。查询处理器将被设计为接受条款作为输入，因为子句是查询的典型形式。纽黑文大学和奥尔巴尼纽约州立大学的学生将是活跃的参与者。拟议活动的更广泛的影响该项目的RUI组成部分将由本科生在纽黑文大学进行广泛参与。将向学生介绍自动推论和知识汇编的基本思想，并将在原型系统上工作。目的是通过让学生参与有助于真实出版物的实际研究来激发他们的灵感。 PI致力于吸引才华横溢的年轻男女进入数学和计算机科学，并为研究生院做准备。奥尔巴尼大学拥有一项强大的计算机科学研究生课程，奥尔巴尼的PI致力于为学生做好研究的准备。项目网页：http：//www.cs.albany.edu/~nvm/ritries/ erikRosenthal的网页：http：//www.newhaven.edu/show.edu/show.asp?durki = 1623 Neil Murray的网页：