A Language-Theoretical Approach to Descriptive Complexity

Michaël Cadilhac

Sala Javier Pinto, DCC, Campus San Joaquín, PUC

10:00 03/11/2017

We propose a language-theoretical framework in which natural classes are expressed as the closure of some base languages under language operations (natural classes include PTime, AC⁰, and pretty much any class with a complete problem).  To that end, we study what are the essential building blocks in one specific framework: first-order descriptive complexity, in which formulas are used to describe the words belonging to a language.
In this blackboard talk, I will first focus on motivating an unusual move: shifting from words to "hyperwords", that are labeling of hypercubes.  Then I will introduce the language operations needed for our characterizations; the main one is reminiscent of the algebraic block product.  Multiple examples will brighten up an otherwise slightly technical talk.
Joint work with A. Krebs and K-J. Lange, appearing in DLT'16.