文章基本信息

标题：Combinatorial Expressions and Lower Bounds
本地全文：下载
作者：Thomas Colcombet ; Amaldev Manuel
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：249-261
DOI：10.4230/LIPIcs.STACS.2015.249
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：expressions; lower bound; indefinability