Abstract: Knowledge Compilation with Fast Response


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/