On the fixed-parameter tractability of the equivalence test of monotone normal forms
type: Item
instance of: scholarly article
title: On the fixed-parameter tractability of the equivalence test of monotone normal forms
zbMATH Open document ID: 1184.68662
author: Matthias Hagen
published in: Information Processing Letters
publication date: 2010-03-24T00:00:00Z
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5686408
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: equivalence test
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: monotone normal forms
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.03.009
OpenAlex ID: W2011997521
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: The complexity of minimum partial truth assignments and implication in negation-free formulae
cites work: Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: Q4708957
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: How to assign votes in a distributed system
cites work: Q4320535
cites work: On generating all maximal independent sets
cites work: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
cites work: An Efficient Algorithm for the Transversal Hypergraph Generation
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: The Maximum Latency and Identification of Positive Boolean Functions
cites work: On the complexity of inferring functional dependencies
cites work: Q5710169
cites work: NP-completeness: A retrospective
cites work: Q5822054
DOI: 10.1016/J.IPL.2007.03.009
description: scientific article