Abstract
The reduced implicate trie, introduced in [11], is a data structure that may be used as a target language for knowledge compilation. It has the property that, even when large, it guarantees fast response to queries. Specifically, a query can be processed in time linear in the size of the query regardless of the size of the compiled knowledge base.
The knowledge compilation paradigm typically assumes that the “intractable part” of the processing be done once, during compilation. This assumption could render updating the knowledge base infeasible if recompilation is required. The ability to install updates without recompilation may therefore considerably widen applicability.
In this paper, several update operations not requiring recompilation are developed. These include disjunction, substitution of truth constants, conjunction with unit clauses, reordering of variables, and conjunction with clauses.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Coudert, O., Madre, J.: Implicit and incremental computation of primes and essential implicant primes of boolean functions. In: Proceedings of the 29th ACM/IEEE Design Automation Conference, pp. 36–39 (1992)
Darwiche, A., Marquis, P.: A knowledge compilation map. Journal of Artificial Intelligence Research 17, 229–264 (2002)
de Kleer, J.: An improved incremental algorithm for computing prime implicants. In: Proceedings of AAAI-92, San Jose, CA, pp. 780–785 (1992)
Hähnle, R., Murray, N.V., Rosenthal, E.: Normal Forms for Knowledge Compilation. In: Hacid, M.-S., Murray, N.V., Raś, Z.W., Tsumoto, S. (eds.) ISMIS 2005. LNCS (LNAI), vol. 3488, Springer, Heidelberg (2005)
Jackson, P., Pais, J.: Computing prime implicants. In: Stickel, M.E. (ed.) 10th International Conference on Automated Deduction. LNCS, vol. 449, Springer, Heidelberg (1990)
Jackson, P.: Computing prime implicants incrementally. In: Kapur, D. (ed.) Automated Deduction - CADE-11. LNCS, vol. 607, Springer, Heidelberg (1992)
Kautz, H., Selman, B.A.: general framework for knowledge compilation, in Proceedings of the International Workshop on Processing Declarative Knowledge (PDK), Kaiserslautern, Germany (July 1991)
Kean, A., Tsiknis, G.: An incremental method for generating prime implicants/implicates. Journal of Symbolic Computation 9, 185–206 (1990)
Kean, A., Tsiknis, G.: Assumption based reasoning and clause management systems. Computational Intelligence 8(1), 1–24 (1992)
Morrison, D.R.: PATRICIA— practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM 15(4), 34–514 (1968)
Murray, N.V., Rosenthal, E.: Efficient query processing with compiled knowledge bases. In: Beckert, B. (ed.) TABLEAUX 2005. LNCS (LNAI), vol. 3702, Springer, Heidelberg (2005)
Murray, N.V., Rosenthal, E.: Efficient Query Processing with Reduced Implicate Tries. Journal of Automated Reasoning (to appear)
Ngair, T.A.: new algorithm for incremental prime implicate generation. In: Proc of IJCAI-93, Chambery, France (1993)
Przymusinski, T.C.: An algorithm to compute circumscription. Artificial Intelligence 38, 49–73 (1989)
Ramesh, A., Becker, G., Murray, N.V.: CNF and DNF considered harmful for computing prime implicants/implicates. Journal of Automated Reasoning 18(3), 337–356 (1997)
Reiter, R., de Kleer, J.: Foundations of assumption-based truth maintenance systems: preliminary report. In: Proceedings of the 6th National Conference on Artificial Intelligence, Seattle, WA , pp. 183–188 (July 12-17 1987)
Slagle, J.R., Chang, C.L., Lee, R.C.T.: A new algorithm for generating prime implicants. IEEE transactions on Computers 19(4), 304–310 (1970)
Strzemecki, T.: Polynomial-time algorithm for generation of prime implicants. Journal of Complexity 8, 37–63 (1992)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Murray, N.V., Rosenthal, E. (2007). Updating Reduced Implicate Tries. In: Olivetti, N. (eds) Automated Reasoning with Analytic Tableaux and Related Methods. TABLEAUX 2007. Lecture Notes in Computer Science(), vol 4548. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73099-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-73099-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73098-9
Online ISBN: 978-3-540-73099-6
eBook Packages: Computer ScienceComputer Science (R0)