On the fixed-parameter tractability of the equivalence test of monotone normal forms

DOI10.1016/J.IPL.2007.03.009zbMATH Open1184.68662OpenAlexW2011997521MaRDI QIDQ2379965FDOQ2379965

Authors: Matthias Hagen 

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.009

Recommendations

• How to apply SAT-solving for the equivalence test of monotone normal forms
• Mathematical Foundations of Computer Science 2005
• Complexity of DNF minimization and isomorphism testing for monotone formulas
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• Experimental comparison of the two Fredman-Khachiyan-algorithms

zbMATH Keywords

computational complexityanalysis of algorithmsfixed-parameter tractabilityequivalence testmonotone normal forms

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Title not available (Why is that?)
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of inferring functional dependencies
• How to assign votes in a distributed system
• On generating all maximal independent sets
• NP-completeness: A retrospective
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Complexity of identification and dualization of positive Boolean functions
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions
• Title not available (Why is that?)
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Title not available (Why is that?)
• The complexity of minimum partial truth assignments and implication in negation-free formulae

Cited In (3)

• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• How to apply SAT-solving for the equivalence test of monotone normal forms
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem

This page was built for publication: On the fixed-parameter tractability of the equivalence test of monotone normal forms

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