Ninth Annual IEEE Symposium on

Logic in Computer Science (LICS 1994)

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

Authors: Lauri Hella Phokion Kolaitis Kerkko Luosto


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 ℒ∞ww 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


    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}