2026-07-20T14:53:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4918 2024-03-06T10:35:33Z ddc:004 open_access

Combinatorial Expressions and Lower Bounds Colcombet, Thomas Manuel, Amaldev expressions lower bound indefinability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Amaldev Manuel 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.249 urn:nbn:de:0030-drops-49181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.249 eng https://creativecommons.org/licenses/by/3.0/legalcode