COMPUTER SCIENCE COLLOQUIUM

On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width

Klaus Meer Brandenburg University of Technology

Tuesday, 29 September, 2009 at 14:15 IMADA's Seminar Room

ABSTRACT

We study the expressive power of certain families of polynomials with coefficients in a field K. The latter are defined via Boolean formulas in conjunctive normal form. We attach in a natural way a graph to such a formula and study the resulting polynomial families when certain parameters of that graph like tree- and clique-width are assumed to bounded.

This is joint work with I. Briquel and P. Koiran from ENS Lyon.

Host: Kim Skak Larsen

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle