Complexity of DNF minimization and isomorphism testing for monotone formulas
type: Item
instance of: scholarly article
title: Complexity of DNF minimization and isomorphism testing for monotone formulas
zbMATH Open document ID: 1152.68021
author: J. Goldsmith
author: Matthias Hagen
author: Martin Mundhenk
published in: Information and Computation
publication date: 2008-08-22T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5315340
zbMATH Keywords: computational complexity
zbMATH Keywords: monotone formulas
zbMATH Keywords: prime implicants
zbMATH Keywords: formula isomorphism
MaRDI profile type: Publication
full work available at URL: j.ic.2008.03.002
OpenAlex ID: W2028124393
cites work: The Formula Isomorphism Problem
cites work: On the computational complexity of some classical equivalence relations on boolean functions
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: Mathematical Foundations of Computer Science 2005
cites work: On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
cites work: On generating all maximal independent sets
cites work: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
cites work: Log Space Recognition and Translation of Parenthesis Languages
cites work: Q4298260
cites work: The complexity of facets (and some facets of complexity)
cites work: Q5822054
cites work: Mathematical Foundations of Computer Science 2003
cites work: The minimum equivalent DNF problem and shortest implicants
cites work: The Complexity of Enumeration and Reliability Problems
DOI: 10.1016/J.IC.2008.03.002
description: scientific article; zbMATH DE number 5315340