In vielen Bereichen der Informatik (Datenbanken, künstliche Intelligenz und weitere) spielen Constraint-basierte Anfragesprachen eine Rolle. Ein Programm in diesem Kontext besteht aus einer Angabe von Einschränkungen, die eine mögliche Lösung erfüllen muss. Eine Ausführung solch eines Programms liefert dann eine Lösung (etwa einen Datenbank-Eintrag), die alle Einschränkungen erfüllt. In diesem Forschungsschwerpunkt werden verschiedene Berechnungsprobleme (etwa das Finden einer Lösung, das Bestimmen der Anzahl aller Lösungen, das Aufzählen aller Lösungen) komplexitätstheoretisch untersucht.

Complexity of Constraints (Dagstuhl-Seminar)

Ausgewählte Publikationen

  1. M. Bauland, E. Böhler, N. Creignou, S. Reith, H. Schnoor, H. Vollmer, The complexity of problems for quantified constraints; Electronic Colloquium on Computational Complexity, TR 07-023, 2007.
  2. E. Böhler, S. Reith, H. Schnoor, H. Vollmer, Bases for Boolean co-clones; Elsevier Information Processing Letters, 96:59-66, 2005.
  3. E. Böhler, N. Creignou, S. Reith, H. Vollmer. Playing with Boolean blocks, part II: constraint satisfaction problems; ACM SIGACT-Newsletter, 35(1):22-35, 2004
  4. E. Böhler, E. Hemaspaandra, S. Reith, H. Vollmer. The complexity of Boolean constraint isomorphism; Proc. 21st Symposium on Theoretical Aspects of Computer Science, Springer Lecture Notes in Computer Science Vol. 2996, 164-175, 2004. Springer-Verlag ACM Computing Research Repository, Technical Report cs.CC/0306134, 2003
  5. E. Böhler, E. Hemaspaandra, S. Reith, H. Vollmer. Equivalence and isomorphism for Boolean constraint satisfaction; Proc. Computer Science Logic, Springer Lecture Notes in Computer Science Vol. 2471, 412-426, 2002
  6. S. Reith, H. Vollmer, Optimal satisfiability for propositional calculi and constraint satisfaction problems; Proc. 25th International Symposium on Mathematical Foundations of Computer Science, Springer Lecture Notes in Computer Science Vol. 1893, 640-649, 2000

Letzte Änderung: 09.01.24