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 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)