ACM/IEEE Symposium on Logic in Computer Science

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

Nineteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2004)

Paper: Equicardinality on Linear Orders (at LICS 2004)

Authors: Kerkko Luosto


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.


    author = 	 {Kerkko Luosto},
    title = 	 {Equicardinality on Linear Orders},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
    year =	 {2004},
    month =	 {July}, 
    pages =      {458--465},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton