Identifying Prime Implicate Branches in Reduced Implicate Tries

• Autorzy: Murray N.V. , Rosenthal E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

reduced implicate tries; prime implicates; knowledge compilation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 2
• Strony: 227--243
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Murray N.V.

autor

Rosenthal E.

• Department of Computer Science, LI-67A, University at Albany - SUNY, Albany, NY 12222 USA,

Bibliografia

• [1] Bittencourt, G.: Combining Syntax and Semantics through Prime Form Representation, Journal of Logic and Computation, 18, 2008, 13-33.
• [2] Coudert, O., Madre, J.: Implicit and incremental computation of primes and essential implicant primes of boolean functions., 29th ACM/IEEE Design Automation Conference, 1992.
• [3] de Kleer, J.: An improved incremental algorithm for computing prime implicants, Proc. AAAI-92, San Jose, CA, 1992.
• [4] Fredkin, E.: Trie memory, Communications of the ACM, 3(9), 1960, 490-499.
• [5] Jackson, P.: Computing prime implicants incrementally, Proc. 11th International Conference on Automated Deduction, Saratoga Springs, NY, June, 1992, 1992, In Lecture Notes in Artificial Intelligence, Springer-Verlag, Vol. 607.
• [6] Jackson, P., Pais, J.: Computing prime implicants, Proc. 10th International Conference on Automated Deductions, Kaiserslautern, Germany, July, 1990, 449, 1990, In Lecture Notes in Artificial Intelligence, Springer-Verlag, Vol. 449.
• [7] Kautz, H., Selman, B.: A general framework for knowledge compilation, Proc. International Workshop on Processing Declarative Knowledge (PDK), Kaiserslautern, Germany, July, 1991, 1991.
• [8] Kean, A., Tsiknis, G.: An incremental method for generating prime implicants/implicates, Journal of Symbolic Computation, 9, 1990, 185-206.
• [9] Kean, A., Tsiknis, G.: Assumption based reasoning and clause management systems, Computational Intelligence, 8(1), 1992, 1-24.
• [10] Manquinho, V., Flores, P., Silva, J., Oliveira, A.: Prime implicant computation using satisfiability algorithms, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, Newport Beach, U.S.A., November, 1997, 1997.
• [11] Morrison, D.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric, Journal of the ACM, 15(4), 1968, 514-534.
• [12] Murray, N., Rosenthal, E.: Efficient query processing with compiled knowledge bases, Proc. International Conference TABLEAUX 2005 - Analytic Tableaux and RelatedMethods, Koblenz, Germany, September 2005, 2005, In Lecture Notes in Artificial Intelligence, Springer-Verlag, Vol. 3702.
• [13] Murray, N., Rosenthal, E.: Efficient query processing with reduced implicate tries, Journal of Automated Reasoning, 38(1-3), 2007, 155-172.
• [14] Murray, N., Rosenthal, E.: Updating reduced implicate tries, Proceedings of the International Conference TABLEAUX 2007 - Analytic Tableaux and Related Methods, Aix en Provence, France, July 2007, 2007, In Lecture Notes in Artificial Intelligence, Springer-Verlag. Vol. 4548.
• [15] Ngair, T.: A new algorithm for incremental prime implicate generation, Proc. IJCAI-93, Chambery, France, (1993), 1993.
• [16] Przymusinski, T. C.: An algorithm to compute circumscription, Artificial Intelligence, 38, 1989, 49-73.
• [17] Ramesh, A., Becker, G., Murray, N. V.: CNF and DNF considered harmful for computing prime implicants/implicates, Journal of Automated Reasoning, 18(3), 1997, 337-356.
• [18] Reiter, R., de Kleer, J.: Foundations of assumption-based truth maintenance systems: preliminary report, Proc. 6th National Conference on Artificial Intelligence, Seattle, WA, (July 12-17, 1987), 1987.
• [19] Slagle, J. R., Chang, C. L., Lee, R. C. T.: A new algorithmfor generating prime implicants, IEEE transactions on Computers, C-19(4), 1970, 304-310.
• [20] Strzemecki, T.: Polynomial-time algorithm for generation of prime implicants, Journal of Complexity, 8, 1992, 37-63.