License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.616
URN: urn:nbn:de:0030-drops-54420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5442/
Go to the corresponding LIPIcs Volume Portal

Paperman, Charles

Finite-Degree Predicates and Two-Variable First-Order Logic

pdf-format:
38.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{paperman:LIPIcs:2015:5442,
  author =	{Charles Paperman},
  title =	{{Finite-Degree Predicates and Two-Variable First-Order Logic}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{616--630},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5442},
  URN =		{urn:nbn:de:0030-drops-54420},
  doi =		{10.4230/LIPIcs.CSL.2015.616},
  annote =	{Keywords: First order logic, automata theory, semigroup, modular predicates}
}

Keywords: First order logic, automata theory, semigroup, modular predicates
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI