Polynomial-time algorithms for generation of prime implicants

DOI10.1016/0885-064X(92)90033-8zbMath0768.68061MaRDI QIDQ1190532

Tadeusz Strzemecki

Publication date: 26 September 1992

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

time complexity; Boolean function; disjunctive normal form; prime implicants; correctness of algorithms; neighborhood cube

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

06E30: Boolean functions

Related Items

Prime implicants of first order formulas via transversal clauses, The Decomposition Tree for analyses of Boolean functions, Efficient query processing with reduced implicate tries, The minimum equivalent DNF problem and shortest implicants

Uses Software

• ESPRESSO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An incremental method for generating prime implicants/implicates
• On the number of prime implicants
• Simplest normal truth functions
• A Way to Simplify Truth Functions
• On simplifying truth-functional formulas
• Algebraic Topological Methods for the Synthesis of Switching Systems. I
• A Local Selection Algorithm for Switching Function Minimization
• Generating Essential Primes for a Boolean Function with Multiple-Valued Inputs
• Generation of Prime Implicants from Subfunctions and a Unifying Approach to the Covering Problem
• Minimization of Switching Functions—A Fast Technique
• MINI: A Heuristic Approach for Logic Minimization
• Generating Test Examples for Heuristic Boolean Minimization
• Minimizability of random Boolean functions
• Maxterm Type Expressions of Switching Functions and Their Prime Implicants
• Fault Detection in Redundant Circuits
• RST Flip-Flop Input Equations
• An Algorithm for the Automatic Approximate Minimization of Boolean Functions
• Partitioned List Algorithms for Prime Implicant Determination from Canonical Forms
• A Numerical Procedure for Determination of the Prime Implicants of a Boolean Function
• A New Algorithm for Generating Prime Implicants
• On Cores and Prime Implicants of Truth Functions
• Recursive Operators for Prime Implicant and Irredundant Normal Form Determination
• Computational Complexity of Partitioned List Algorithms
• Generation of Prime Implicants by Direct Multiplication
• Weighting Method for the Determination of the Irredundant Set of Prime Implicants
• The Problem of Simplifying Truth Functions