Combinatorial Expressions and Lower Bounds
Thomas Colcombet, Amaldev Manuel · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
A new paradigm, called combinatorial expressions, for computing functions expressing properties over infinite domains is introduced. The main result is a generic technique, for showing indefinability of certain functions by the expressions, which uses a result, namely Hales-Jewett theorem, from Ramsey theory. An application of the technique for proving inexpressibility results for logics on metafinite structures is given. Some extensions and normal forms are also presented.