## Paper: How to define a linear order on finite models (at LICS 1994)

Authors:**Lauri Hella Phokion Kolaitis Kerkko Luosto**

### Abstract

We describe on a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain
upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite
model theory such as fixpoint logic (FP), partial fixpoint logic (PFP), infinitary logic ℒ_{∞w}^{w} with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show
that the upper and lower bounds established here can not be improved dramatically, unless outstanding conjectures in complexity
theory are resolved at the same time

### BibTeX

@InProceedings{HellaKolaitisLuosto-Howtodefinealinearo, author = {Lauri Hella and Phokion Kolaitis and Kerkko Luosto}, title = {How to define a linear order on finite models}, booktitle = {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994}, year = 1994, editor = {Samson Abramsky}, month = {July}, pages = {40--49}, location = {Paris, France}, publisher = {IEEE Computer Society Press} }