loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th Annual IEEE Symposium on Logic in Computer Science (LICS'03)
Spectrum Hierarchies and Subdiagonal Functions
Ottawa, Canada
June 22-June 25
ISBN: 0-7695-1884-2
Aaron Hunter, Simon Fraser University
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.
Citation:
Aaron Hunter, "Spectrum Hierarchies and Subdiagonal Functions," lics, pp.281, 18th Annual IEEE Symposium on Logic in Computer Science (LICS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.