Abstract : In this talk we will survey questions in logic and complexity at the interface between finite model theory, algorithms and database theory. The focus will be on the complexity of the many tasks related to query answering such as deciding if a Boolean query (for example a restricted first-order formula) is true or not in a finite model, counting the size of the answer set or enumerating the results. It will be a survey of some of the tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.

Keywords : finite model theory; database theory; complexity