2002 · 17 citations · 18 references
ComputingComputer ScienceFormal MethodsModel FormulationModel TheoryPartial OrdersModel Order ReductionOrder DeterminationOrder RelationTotal Ordering
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 /spl Lscrsub /spl infin/wsup 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
18
Larry J. Stockmeyer · Theoretical Computer Science · 1976 · 1.3K citations
Relational queries computable in polynomial time
Neil Immerman · Information and Control · 1986 · 648 citations
Languages that Capture Complexity Classes
Neil Immerman · SIAM Journal on Computing · 1987 · 545 citations