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

zbMATH Keywords

computational complexityanalysis of algorithmsfixed-parameter tractabilityequivalence testmonotone normal forms

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

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

Cites work

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

Cited in

(4)

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

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)