joint work with Thomas Colcombet

Combinatorial expressions are expressions built using two kinds of functions --- those having bounded arity unbounded domain (e.g. addition of integers), and those having bounded domain and unrestricted arity (e.g. Boolean OR of k inputs, where k is as large as necessary). These expressions are used to separate subclasses of Data automata. For the talk, I will introduce the expressions, discuss some normal forms for them and show how to prove inexpressibility results using tools from Combinatorics (in particular Hales-Jewett theorem). This work will be presented in STACS.