Identifying Prime Implicate Branches in Reduced Implicate Tries

Issue title: Methodologies for Intelligent Systems

Article type: Research Article

Authors: Murray, Neil V. | Rosenthal, Erik

Affiliations: Department of Computer Science, State University of New York Albany, NY 12222, USA. E-mail: [email protected] | Department of Mathematics, University of New Haven West Haven, CT 06516, USA. E-mail: [email protected]

Abstract: The reduced implicate trie is a data structure that was introduced in [12] as a target language for knowledge compilation. It has the property that, even when large, it guarantees that a query can be processed in time linear in the size of the query, regardless of the size of the compiled knowledge base. In this paper, the branches of a reduced implicate trie that correspond to prime implicates are characterized. A technique is developed for finding and marking nodes for which all descending branches correspond to non-prime implicates. This is extended to allow the discovery of prime implicate subsets of queries with a "yes" answer.

Keywords: Reduced implicate tries, prime implicates, knowledge compilation

DOI: 10.3233/FI-2010-247

Journal: Fundamenta Informaticae, vol. 99, no. 2, pp. 227-243, 2010