8 citations · 21 across the 12 of their papers we have counts for
16 papers
From FPT Decision to FPT Enumeration
Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler +1
Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confin…
On the enumeration of signatures of XOR-CNF's
Nadia Creignou, Oscar Defrain, Frédéric Olive +1
Given a CNF formula with clauses over a set of variables , a truth assignment generates a binary sequence $σ_φ(\mathbf{a})=(C…
Complexity of Reasoning with Cardinality Minimality Conditions
Nadia Creignou, Frédéric Olive, Johannes Schmidt
Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the sati…
Enumeration Classes Defined by Circuits
Nadia Creignou, Arnaud Durand, Heribert Vollmer
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration probl…
A Complexity Theory for Hard Enumeration Problems
Nadia Creignou, Markus Kröll, Reinhard Pichler +2
Complexity theory provides a wealth of complexity classes for analyzing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, t…
Belief merging within fragments of propositional logic
Nadia Creignou, Odile Papini, Stefan Rümmele +1
Recently, belief change within the framework of fragments of propositional logic has gained increasing attention. Previous works focused on belief contraction and belief revision o…