loading...
Equicardinality on Linear Orders
Turku, Finland July 13-July 17
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2004.131964019th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.


Suggestions