loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Symposium on Logic in Computer Science (LICS'04)
Equicardinality on Linear Orders
Turku, Finland
July 13-July 17
ISBN: 0-7695-2192-4
Kerkko Luosto, University of Helsinki
Linear orders are of inherent interest in finite model theory, especially in descriptive complexity theory. Here, the class of ordered structures is approached from a novel point of view, using generalized quantifiers as a means of analysis. The main technical result is a characterization of the cardinality quantifiers which can express equicardinality on ordered structures. This result can be viewed as a dichotomy: the cardinality quantifier either shows a lot of periodicity, or is quite non-periodic, the equicardinality quantifier being definable only in the latter case.
The main result shows, once more, that there is a drastic difference between definability among ordered structures and definability on unordered structures. Connections of the result to the descriptive complexity of low-level complexity classes are discussed.
Citation:
Kerkko Luosto, "Equicardinality on Linear Orders," lics, pp.458-465, 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.