Annals of Pure and Applied Logic 87 (3):241-267 (1997)

We carry out 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 least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω 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 cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00008-0
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,295
Through your library

References found in this work BETA

Probabilities on Finite Models.Ronald Fagin - 1976 - Journal of Symbolic Logic 41 (1):50-58.
Fixed-Point Extensions of First-Order Logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
On Moschovakis Closure Ordinals.Jon Barwise - 1977 - Journal of Symbolic Logic 42 (2):292-296.
On Finite Rigid Structures.Yuri Gurevich & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (2):549-562.

View all 12 references / Add more references

Citations of this work BETA

The Dynamic Emergence of Representation.Mark H. Bickhard - 2004 - In Hugh Clapin (ed.), Representation in Mind. Elsevier. pp. 71--90.
Descriptive Complexity of Graph Spectra.Anuj Dawar, Simone Severini & Octavio Zapata - 2019 - Annals of Pure and Applied Logic 170 (9):993-1007.
On Finite Rigid Structures.Yuri Gurevich & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (2):549-562.
Finite Variable Logics in Descriptive Complexity Theory.Martin Grohe - 1998 - Bulletin of Symbolic Logic 4 (4):345-398.

View all 6 citations / Add more citations

Similar books and articles


Added to PP index

Total views
13 ( #743,998 of 2,448,708 )

Recent downloads (6 months)
1 ( #447,803 of 2,448,708 )

How can I increase my downloads?


My notes