All reports by Author Nadia Creignou:

__
TR07-023
| 26th February 2007
__

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor#### The Complexity of Problems for Quantified Constraints

__
TR05-119
| 15th September 2005
__

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini#### Preferred representations of Boolean relations

__
TR05-024
| 8th February 2005
__

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer#### Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini

We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>