Complexity of DNF minimization and isomorphism testing for monotone formulas

DOI10.1016/J.IC.2008.03.002MaRDI QIDQ939444zbMATH OpenOpenAlexFDO

Authors J. Goldsmith, Matthias Hagen, Martin Mundhenk

Publication date 22 August 2008

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2008.03.002

zbMATH Keywords

computational complexityformula isomorphismmonotone formulasprime implicants

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Mathematical Foundations of Computer Science 2005
• The minimum equivalent DNF problem and shortest implicants
• scientific article; zbMATH DE number 3978379
• Minimal implicant and DNF representation
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3085175 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Log Space Recognition and Translation of Parenthesis Languages
• Mathematical Foundations of Computer Science 2003
• Mathematical Foundations of Computer Science 2005
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On generating all maximal independent sets
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the computational complexity of some classical equivalence relations on boolean functions
• The Complexity of Enumeration and Reliability Problems
• The complexity of facets (and some facets of complexity)
• The Formula Isomorphism Problem
• The minimum equivalent DNF problem and shortest implicants

Cited in

(12)

• The minimum equivalent DNF problem and shortest implicants
• The complexity of Bayesian networks specified by propositional and relational languages
• Complexity results for probabilistic answer set programming
• On the fixed-parameter tractability of the equivalence test of monotone normal forms
• Isomorphism testing of read-once functions and polynomials
• Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments
• Minimal implicant and DNF representation
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• Discovery Science
• Mathematical Foundations of Computer Science 2005
• Towards an efficient implementation of a tableau method for reactive safety specifications
• Weightedness measures from inequality systems

This page was built for publication: Complexity of DNF minimization and isomorphism testing for monotone formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q939444)