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.2021.18
URN: urn:nbn:de:0030-drops-134520
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13452/
Dawar, Anuj ; Sankaran, Abhisekh
Extension Preservation in the Finite and Prefix Classes of First Order Logic
| pdf-format: |
|
Abstract
It is well known that the classic Łoś-Tarski preservation theorem fails in the finite: there are first-order definable classes of finite structures closed under extensions which are not definable (in the finite) in the existential fragment of first-order logic. We strengthen this by constructing for every n, first-order definable classes of finite structures closed under extensions which are not definable with n quantifier alternations. The classes we construct are definable in the extension of Datalog with negation and indeed in the existential fragment of transitive-closure logic. This answers negatively an open question posed by Rosen and Weinstein.
BibTeX - Entry
@InProceedings{dawar_et_al:LIPIcs:2021:13452,
author = {Anuj Dawar and Abhisekh Sankaran},
title = {{Extension Preservation in the Finite and Prefix Classes of First Order Logic}},
booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
pages = {18:1--18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-175-7},
ISSN = {1868-8969},
year = {2021},
volume = {183},
editor = {Christel Baier and Jean Goubault-Larrecq},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13452},
URN = {urn:nbn:de:0030-drops-134520},
doi = {10.4230/LIPIcs.CSL.2021.18},
annote = {Keywords: finite model theory, preservation theorems, extension closed, composition, Datalog, Ehrenfeucht-Fraisse games}
}
| Keywords: | finite model theory, preservation theorems, extension closed, composition, Datalog, Ehrenfeucht-Fraisse games | |
| Seminar: | 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 13.01.2021 |
