A New Algorithm for Incremental Prime Implicate Generation
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 46-50.
Abstract
Traditional algorithms for prime implicate generation [Quine, 1952; McCluskey, 1956; Tison, 1967; Kean and Tsiknis, 1990; de Kleer, 1992] require the input formulas to be first transformed into a CNF formula. This process, however, requires exponential time in the worst case and can result in an exponential blow up of the input size. Such cases occur frequently when the problem domains are best characterized by some DNF formulas . In this paper, we study a new algorithm which allows a more general input: a conjunction ofDNF formulas. We will present empirical results comparing the new algorithm with some existing implementations, and discuss how it can be used in a propositional abductive reasoning system.
@inproceedings{ijcai1993p7,
title = {A New Algorithm for Incremental Prime Implicate Generation},
author = {Ngair, Teow-Hin},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {46--50},
year = {1993},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1993/7},
}
TY - CPAPER TI - A New Algorithm for Incremental Prime Implicate Generation AU - Ngair, Teow-Hin T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 46 EP - 50 UR - https://ijcai.org/proceedings/1993/7 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
