Second Order Logic over Finite Structures -- Report on a Research Program

Second Order Logic over Finite Structures - Report on a Research Program. Abstract: This talk reports about the results achieved so far in the context of a research programme in the intersection of logic, formal language theory, and complexity theory. The aim of this research programme is to classify the complexity of evaluating formulas from different prefix classes of second-order logic over diferent types of finite structures, such as strings, graphs, or arbitrary structures. In particular, we report on classifications of existential second-order logic on graphs.