The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
type: Item
instance of: scholarly article
title: The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
zbMATH Open document ID: 1099.68040
author: Hans Kleine Büning
author: Daoyun Xu
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2005-05-13T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 2168186
zbMATH Keywords: complexity
zbMATH Keywords: renaming
zbMATH Keywords: homomorphism
zbMATH Keywords: minimal unsatisfiable formula
zbMATH Keywords: graph isomorphism
MaRDI profile type: Publication
full work available at URL: s10472-005-0422-8
OpenAlex ID: W4256737158
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
cites work: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
cites work: On the complexity of H-coloring
cites work: Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.
cites work: Q4273947
cites work: Short proofs for tricky formulas
cites work: The complexity of facets resolved
cites work: Homomorphisms of conjunctive normal forms.
cites work: The symmetry rule in propositional logic
DOI: 10.1007/S10472-005-0422-8
Recommended article: Q3434502
Recommended article: Q5309031
Recommended article: On the size of minimal unsatisfiable formulas
Recommended article: Q5473177
Recommended article: The complexity of minimal satisfiability problems
Recommended article: Q2762521
Recommended article: The complexity of homomorphism and constraint satisfaction problems seen from the other side
Recommended article: Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.
Recommended article: Minimally unsatisfiable \(CNF\) formulas
Recommended article: On subclasses of minimal unsatisfiable formulas
description: scientific article; zbMATH DE number 2168186