Title: On the Complexity of Monadic Second-Order Logic and its Applications
Speaker: Michael Elberfeld, International Computer Science Institute in Berkeley
Date: Wednesday, July 10, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The complexity of evaluating a formula in predicate logic highly depends on the considered formula. Evaluating a formula from monadic second-order (MSO) logic can be NP-complete, while evaluating any first-order (FO) formula can be done in P. Another aspect that influences the complexity of evaluating formulas is the kind of input structures considered. Any MSO-formula can be solved by a linear-time algorithm on structures of bounded tree width, and the same bound holds for any FO-formula and structures whose tree width is bounded locally. While these upper bounds are optimal from the algorithmic point of view, in my talk I will outline an ongoing effort to find optimal upper bounds from the complexity-theoretic point of view. That means, to refine polynomial-time bounds in terms of circuit and space-efficient computations. Many problems that are studied in the realm of complexity classes like TC0, NC1, L, and LOGCFL are MSO-definable. Using their MSO-definitions not only unifies these problems, but also makes it easier to prove upper bounds via techniques for balancing tree decompositions and automata-based methods.
Short Bio:
Michael Elberfeld is a postdoctoral research fellow at the International Computer Science Institute in Berkeley. He completed his PhD in 2012 at the University of Luebeck in Germany where he worked on bioinformatics algorithms and later became interested in the computational complexity and model theory of monadic second-order logic. While in Berkeley, he works on better understanding the space complexity of reachability problems.