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

项目名称：快速响应PI的知识编译：这个项目关注的是索引结构的开发、维护和利用--减少的隐含尝试（ri-tries）--它回答了大型数据库的逻辑查询。 该项目的主要目标是进一步发展tri-trie，识别和分类的数据库，这些尝试将是有效的，和发展的计算机系统，实现tri-trie。减少隐含trie是一种数据结构存储在计算机上的命题数据库。 对查询的快速响应是通过使其易于确定数据库的结果（具有是答案的查询）来实现的。 从技术上讲，一旦数据库被编译成ri-trie，对任何查询的响应时间都保证与查询的大小成线性关系，而不管编译的数据库的大小。 这个响应时间代表了性能和空间之间的折衷，因为响应时间可能很大。 这个项目的一个中心焦点将是确定什么类型的数据库适合于尝试。 这将通过实验和理论的发展来实现。一个原型系统，编译逻辑公式成ritries和查询处理模块将被开发。 最初，该系统将被设计用于合取范式的数据库;从长远来看，任何来自命题逻辑的公式都将是可接受的输入。 查询处理器将被设计为接受子句作为输入，因为子句是查询的典型形式。 纽黑文大学和纽约州立大学奥尔巴尼分校的学生将积极参与。拟议活动的更广泛影响这个项目的RUI部分将是纽黑文大学本科生的广泛参与。 学生将被介绍到自动演绎和知识汇编的基本思想，并将在原型系统上工作。我们的目标是通过让学生参与到真实的研究中来激励他们，从而为真实的出版物做出贡献。 PI致力于吸引有才华的年轻男女进入数学和计算机科学，并为他们准备研究生院。 奥尔巴尼大学有一个强大的计算机科学研究生课程，奥尔巴尼的PI致力于为学生的研究生涯做好准备。项目网页：http://www.cs.albany.edu/~nvm/ritries/Erik Rosenthal的网页：http://www.newhaven.edu/show.asp? durki= 1623尼尔·默里的网页：http://www.cs.albany.edu/~nvm/

Project Title: Knowledge Compilation with Fast ResponsePIs: 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 systemwill 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 ActivityThe 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=1623Neil Murray's Web Page: http://www.cs.albany.edu/~nvm/