Invited talk: Monadic Second-Order Definable Problems in Computational Complexity Theory

Applying problem definitions in terms of monadic-second order (MSO) formulas in conjunction with evaluation procedures for tree-width-bounded graphs and reductions to them is a common approach to design efficient algorithms. Beside simplifying known proofs, this algorithmic paradigm has proven to help develop new efficient algorithms. Just like many problems in algorithmics are MSO-definable, the same is true for a large number of problems studied in the realm of parallel and space complexity classes inside deterministic polynomial time. Thus, understanding the fine-grained complexity-theoretic aspects of evaluating formulas in MSO-logic as well as its restrictions and generalizations has a great potential. The talk first surveys recent developments on approaches for evaluating MSO-formulas on tree-width-bounded graphs in terms of uniform circuits and logarithmic space. Then current and possible future complexity-theoretic applications for MSO-definitions and tree width reductions are discussed. 10: 00 10: 30 Breakfast & coffee

Authors

• Michael Elberfeld

Keywords

No keywords are indexed for this paper.