文章基本信息

标题：Finite-Degree Predicates and Two-Variable First-Order Logic
本地全文：下载
作者：Charles Paperman
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：41
页码：616-630
DOI：10.4230/LIPIcs.CSL.2015.616
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature. Replacing finite-degree by arbitrary numerical predicates in the statement would entail a long standing conjecture on the circuit complexity of the addition function. Thus, this result can be viewed as a uniform version of this circuit lower bound.
关键词：First order logic; automata theory; semigroup; modular predicates