## Paper: Equicardinality on Linear Orders (at LICS 2004)

Authors:**Kerkko Luosto**

### Abstract

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.

### BibTeX

@InProceedings{Luosto-EquicardinalityonLi, author = {Kerkko Luosto}, title = {Equicardinality on Linear Orders}, booktitle = {Proceedings of the Nineteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2004}, year = 2004, editor = {Harald Ganzinger}, month = {July}, pages = {458--465}, location = {Turku, Finland}, publisher = {IEEE Computer Society Press} }