Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/18319

Title: On the variable hierarchy of first-order spectra
Authors: TAN, Tony
Kopzcynski, Eryk
Issue Date: 2015
Citation: ACM Transactions on Computational Logic, 16 (2)
Abstract: The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variable. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations.
Notes: Kopczynski, E (reprint author), Univ Warsaw, PL-00325 Warsaw, Poland. erykk@mimuw.edu.pl; ptony.tan@gmail.com
URI: http://hdl.handle.net/1942/18319
DOI: 10.1145/2733376
ISI #: 000353644400008
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
article366.9 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.