During the last forty years logics over nite structures have become a central pillar for studying the denability and complexity of computational problems. The focus is on understanding how the expressive power of logics over nite structures, or equivalently query languages over relational databases, relate to natural classes of computational complexity
|