Advertisement
Published in:
2009 | OriginalPaper | Chapter
Prime Implicates and Reduced Implicate Tries
Authors : Neil V. Murray, Erik Rosenthal
Published in: Foundations of Intelligent Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The reduced implicate trie (
ri
-trie) is a data structure that was introduced as a target language for knowledge compilation. It has the property that, even when large, it guarantees fast response to queries. It also has the property that each prime implicate of the formula it represents corresponds to a branch. In this paper, those prime branches are characterized, and a technique is developed for marking nodes to identify branches that correspond to non-prime implicates. This marking technique is enhanced to allow discovery of prime implicate subsets of queries that are answered affirmatively.