Switch to: References

Citations of:

Upper and Lower Bounds for First Order Expressibility

Journal of Symbolic Logic 54 (1):287-288 (1989)

Add citations

You must login to add citations.

Hierarchies in transitive closure logic, stratified Datalog and infinitary logic.Erich Grädel & Gregory L. McColm - 1996 - Annals of Pure and Applied Logic 77 (2):169-199.details We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of (...) Download Export citation Bookmark 4 citations
Generalized quantifiers and pebble games on finite structures.Phokion G. Kolaitis & Jouko A. Väänänen - 1995 - Annals of Pure and Applied Logic 74 (1):23-75.details First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) Download Export citation Bookmark 21 citations
Guarded quantification in least fixed point logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.details We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor. Download Export citation Bookmark
Parametrization over inductive relations of a bounded number of variables.Gregory L. McColm - 1990 - Annals of Pure and Applied Logic 48 (2):103-134.details Download Export citation Bookmark 4 citations
How to define a linear order on finite models.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1997 - Annals of Pure and Applied Logic 87 (3):241-267.details 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 (...) Download Export citation Bookmark 6 citations
Canonization for two variables and puzzles on the square.Martin Otto - 1997 - Annals of Pure and Applied Logic 85 (3):243-282.details We consider infinitary logic with only two variable symbols, both with and without counting quantifiers, i.e. L2 L∞ω2 and C2 L∞ω2mεω. The main result is that finite relational structures admit canonization with respect to L2 and C2: there are polynomial time com putable functors mapping finite relational structures to unique representatives of their equivalence class with respect to indistinguishability in either of these logics. In fact we exhibit in verses to the natural invariants that characterize structures up to L2- or (...) Download Export citation Bookmark 2 citations
Lower bound results on lengths of second-order formulas.Bruno Scarpellini - 1985 - Annals of Pure and Applied Logic 29 (1):29-58.details Download Export citation Bookmark
Asymptotic probabilities of extension properties and random l -colourable structures.Vera Koponen - 2012 - Annals of Pure and Applied Logic 163 (4):391-438.details Download Export citation Bookmark 7 citations
When is arithmetic possible?Gregory L. McColm - 1990 - Annals of Pure and Applied Logic 50 (1):29-51.details When a structure or class of structures admits an unbounded induction, we can do arithmetic on the stages of that induction: if only bounded inductions are admitted, then clearly each inductively definable relation can be defined using a finite explicit expression. Is the converse true? We examine evidence that the converse is true, in positive elementary induction . We present a stronger conjecture involving the language L consisting of all L∞ω formulas with a finite number of variables, and examine a (...) Download Export citation Bookmark 3 citations

1