Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Eighteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2003)

Paper: Spectrum Hierarchies and Subdiagonal Functions (at LICS 2003)

Authors: Aaron Hunter

Abstract

The spectrum of a first-order sentence is the set of cardinalities of its finite models. Relatively little is known about the subclasses of spectra that are obtained by looking only at sentences with a specific signature. In this paper, we study natural subclasses of spectra and their closure properties under simple subdiagonal functions. We show that many natural closure properties turn out to be equivalent to the collapse of potential spectrum hierarchies. We prove all of our results using explicit transformations on first-order structures.

BibTeX

  @InProceedings{Hunter-SpectrumHierarchies,
    author = 	 {Aaron Hunter},
    title = 	 {Spectrum Hierarchies and Subdiagonal Functions},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)},
    year =	 {2003},
    month =	 {June}, 
    pages =      {281--290},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski