Complexity of DNF minimization and isomorphism testing for monotone formulas
From MaRDI portal
Publication:939444
DOI10.1016/j.ic.2008.03.002zbMath1152.68021OpenAlexW2028124393MaRDI QIDQ939444
Matthias Hagen, Judy Goldsmith, 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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
Isomorphism testing of read-once functions and polynomials ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Complexity results for probabilistic answer set programming
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- On generating all maximal independent sets
- On the computational complexity of some classical equivalence relations on boolean functions
- The minimum equivalent DNF problem and shortest implicants
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- The Complexity of Enumeration and Reliability Problems
- Log Space Recognition and Translation of Parenthesis Languages
- The Formula Isomorphism Problem
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Mathematical Foundations of Computer Science 2003
- Mathematical Foundations of Computer Science 2005
This page was built for publication: Complexity of DNF minimization and isomorphism testing for monotone formulas
