NP-completeness of small conflict set generation for congruence closure
type: Item
instance of: scholarly article
title: NP-completeness of small conflict set generation for congruence closure
zbMATH Open document ID: 1377.68090
author: Andreas Fellner
author: Pascal Fontaine
author: Bruno Woltzenlogel Paleo
published in: Formal Methods in System Design
publication date: 2018-01-08T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6823094
zbMATH Keywords: satisfiability modulo theories
zbMATH Keywords: decision procedures
zbMATH Keywords: congruence closure
zbMATH Keywords: complexity
describes a project that uses: Skeptik
MaRDI profile type: Publication
full work available at URL: s10703-017-0283-x
OpenAlex ID: W2693644836
Wikidata QID: Q59521641
cites work: Variations on the Common Subexpression Problem
cites work: Q4428300
cites work: Fast Decision Procedures Based on Congruence Closure
cites work: Term Rewriting and Applications
cites work: Fast congruence closure and extensions
DOI: 10.1007/S10703-017-0283-X
Recommended article: Approximation of coNP sets by NP-complete sets
Recommended article: The complexity of constraint satisfaction problems for small relation algebras
Recommended article: Small Generating Sets and DLPC Problem
Recommended article: On the Complexity of Computing Generators of Closed Sets
Recommended article: Faster and Simpler Minimal Conflicting Set Identification
Recommended article: Q3785940
Recommended article: On the Minimal Constraint Satisfaction Problem: Complexity and Generation
Recommended article: Congruence Closure of Compressed Terms in Polynomial Time
Recommended article: Approximately propagation complete and conflict propagating constraint encodings
Recommended article: On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
description: scientific article; zbMATH DE number 6823094