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.