Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes
Coudert, Olivier ; Madre, Jean-Christophe
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 125-149 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_2_125_0,
     author = {Coudert, Olivier and Madre, Jean-Christophe},
     title = {Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions bool\'eennes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {125-149},
     mrnumber = {1282249},
     zbl = {0890.68089},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_2_125_0}
}

Coudert, Olivier; Madre, Jean-Christophe. Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 125-149. http://gdmltest.u-ga.fr/item/ITA_1994__28_2_125_0/

1. S. B. Akers, Binary Decision Diagrams, IEEE Trans. on Computers, 1978, vol. C-27. | Zbl 0377.94038

2. T. C. Bartee, I. L. Lebow, I. S. Reed, Theory and Design of Digital Machines, McGraw-Hill, 1962. | MR 154452 | Zbl 0114.06504

3. J.-P. Billon, Perfect Normal Forms for Discrete Functions, BULL Research Report n° 87019, juin 1987.

4. N. N. Biswas, Introduction to Logic and Switching Theory, Gordon & Breach Science, 1975. | Zbl 0314.94021

5. R. E. Brayton, G. D. Hachtel, C. T. Mcmullen, A. L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, 1984. | Zbl 0565.94020

6. F. M. Brown, Boolean Reasoning, Kluwer Academic Publishers, 1990. | MR 1166188 | Zbl 0719.03002

7. R. E. Bryant, Graph-Based Algorithms for Boolean Functions Manipulation, IEEE Trans. on Computers, 1986, vol. C35. | Zbl 0593.94022

8. R. E. Bryant, On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication, Carnegie Mellon University Research Report, September 1988.

9. K. M. Butler, D. E. Ross, R. Kapur, M. R. Mercer, Heuristics to Compute Variable Orderings for Efficient Manipulations of Ordered Binary Decision Diagrams, in Proc. of 28th Design Automation Conference, San Francisco, California, June 1991, 417-420.

10. O. Coudert, J. C. Madre, A Unified Framework for the Formal Verification of Sequential Circuits, Proc. of ICCAD '90, novembre 1990, Santa Clara CA, U.S.A.

11. O. Coudert, S.I.A.M.: Une boîte à outils pour la preuve formelle de systèmes séquentiels, Thèse de troisième cycle, École Nationale Supérieure des Télécommunications, Paris, France, octobre 1991.

12. O. Coudert, J. C. Madre, A New Method to Compute Prime and Essential Prime Implicants of Boolean Functions, Proc. of Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, mars 1992, Cambridge MA, U.S.A.

13. O. Coudert, J. C. Madre, Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions, Proc. of 29th DAC, juin 1992, Anaheim CA, U.S.A.

14. O. Coudert, J. C. Madre, A New Implicit DAG Based Prime and Essential Prime Computation Technique, Proc. of International Symposium on Information Sciences, juillet 1992, Fukuoka, Japon.

15. M. Davis, H. Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, 1960, vol. 7, 201-215. | MR 134439 | Zbl 0212.34203

16. S. J. Friedman, K. J. Supowit, Finding the Optimal Variable Ordering for Binary Decision Diagrams, IEEE Trans. on Computer, 1990, vol. C-39, 710-713. | MR 1059769

17. D. F. Hasl, Advanced Concepts in Fault Tree Analysis, Proc. of System Safety Symposium, juin 1965, Seatle.

18. S. J. Hong, S. Muroga, Absolute Minimization of Completely Specified Switching Functions, IEEE Trans. on Computers, 1991, vol. 40, 53-65. | MR 1093496

19. H. R. Hwa, A Method for Generating Prime Implicants of a Boolean Expression, IEEE Trans. on Computers, 1974, 637-641. | MR 441563 | Zbl 0281.94025

20. H. Y. Hwang, D. S. Chao, M. E. Valdez, A New Technique for the Minimization of Switching Functions, IEEE Southeastcon'85, 1985, 299-304.

21. J. De Kleer, An Assumption-Based TMS, Artificial Intelligence, 1986, vol. 28, 127-162.

22. J. De Kleer, B. C. Williams, Diagnosing Multiple Faults, Artificial Intelligence, 1987, vol. 32, 97-130. | Zbl 0642.94045

23. M. C. Loui, G. Bilardi, The Correctness of Tison's Method for Generating Prime Implicants, Report R-952, UILU-ENG 82-2218, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1982.

24. E. L. Jr. Mccluskey, Minimization of Boolean Functions, Bell System Techniques, 1959, vol. 35, 1417-1444. | MR 82876

25. J. C. Madre, J. P. Billon, Proving Circuit Correctness Using Formal Comparison Between Expected and Extracted Behaviour, Proc. of the 25th DAC, juillet 1988, Anaheim CA, U.S.A.

26. J. C. Madre, O. Coudert, A Logically Complete Reasoning Maintenance System Based on Logical Constrain Solver, Proc. of IJCAI'91, août 1991, Sydney, Australia. | Zbl 0747.68072

27. S. Malik, A. R. Wang, R. K. Brayton, A. Sangiovanni-Vincentelli, Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment, Proc. of ICCAD'88, Santa Clara, 1988, U.S.A.

28. S. Minato, N. Ishiura, S. Yajima, Shared Binary Decision Diagrams with Attributed Edges for Efficient Boolean Function Manipulation, Proc. of the 27 th Design Automation Conference, June 1990, Las Vegas, Nevada, 52-57.

29. A. Pagès, M. Gondran, Fiabilité des systèmes, Eyrolles, 1980. | MR 596408 | Zbl 0491.90029

30. W. V. O. Quine, The Problem of Simplifying Truth Functions, American Mathematics Monthly, 1952, vol. 59, 521-531. | MR 51191 | Zbl 0048.24503

31. W. V. O. Quine, A Way to Simplify Truth Functions, American Mathematics. Monthly, 1955, vol. 62, 627-631. | MR 75886 | Zbl 0068.24209

32. W.V. O. Quine, On Cores and Prime Implicants of Truth Functions, American Mathematics Monthly, 1959, vol. 66. | MR 108439 | Zbl 0201.32203

33. R. Reiter, A Theory of Diagnosis From First Principles, Artificial Intelligence, 1987, vol.32. | MR 884192 | Zbl 0643.68122

34. R. Reiter, J. De Kleer, Foundation of Assumption-Based Truth Maintenance Systems: Preliminary Report, Proc. of 6th AAAI, 1987, 183-188.

35. V. T. Rhyne, P. S. Noe, M. H. Mckinney, U. W. Pooch, A New Technique for the Fast Minimization of Switching Functions, IEEE Trans, on Computers, 1977, vol. C-26/8, 757-764. | MR 530246 | Zbl 0365.94048

36. J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of ACM, 1965, vol. 12, 23-41. | MR 170494 | Zbl 0139.12303

37. J. P. Roth, Algebraic Topological Methods for the Synthesis of Switching Systems, Trans. of American Mathematical Society, 1958, vol. 88/2, 301-326. | MR 97285 | Zbl 0083.13103

38. R. L. Rudell, A. L. Sangiovanni-Vincentelli, Multiple Valued Minimization for PLA Optimization, IEEE Trans. on CAD, 1987, vol 6, 727-750.

39. T. Sasao, An Application of Multiple-Valued Logic to a Design of Programmable Logic Arrays, Proc. of 8th Int'l Symposium on Multiple Valued Logic, 1978. | MR 565416

40. J. R. Slage, C. L. Chang, R. C. T. Lee, Completeness Theorems for Semantics Resolution in Consequence Finding, Proc. of IJCAI'69, 1969, 281-285.

41. J. R. Slage, C. L. Chang, R. C. T. Lee, A New Algorithm for Generating Prime Implicants, IEEE Trans, on Computers, 1970, vol. C-19(4), 304-310. | MR 456994 | Zbl 0197.14601

42. M. Stone, The Theory of Representations for Boolean Algebra, Trans. Amer. Math. Soc., 1936, vol. 40, 37-111. | JFM 62.0033.04 | MR 1501865

43. P. Tison, Generalized Consensus Theory and Application to the Minimization of Boolean Functions, IEEE Trans, on Electronic Computers, 1967, vol. EC-16/4, 446-456. | Zbl 0158.16102

44. A. Villemeur, Sûreté de fonctionnement des systèmes industriels, Eyroles, 1988.

45. S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Microelectronics Center of North Carolina, January 1991.