8 found
Order:
  1.  4
    Parametrization Over Inductive Relations of a Bounded Number of Variables.Gregory L. McColm - 1990 - Annals of Pure and Applied Logic 48 (2):103-134.
  2.  17
    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.
    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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  7
    When is Arithmetic Possible?Gregory L. McColm - 1990 - Annals of Pure and Applied Logic 50 (1):29-51.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  7
    Eventual Periodicity and ``One-Dimensional'' Queries.Gregory L. McColm - 1992 - Notre Dame Journal of Formal Logic 33 (2):273-290.
  5.  3
    Dimension Versus Number of Variables, and Connectivity, Too.Gregory L. McColm - 1995 - Mathematical Logic Quarterly 41 (1):111-134.
    We present game-theoretic characterizations of the complexity/expressibility measures “dimension” and “the number of variables” as Least Fixed Point queries. As an example, we use these characterizations to compute the dimension and number of variables of Connectivity and Connectivity.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  7
    Some Ramsey Theory in Boolean Algebra for Complexity Classes.Gregory L. McColm - 1992 - Mathematical Logic Quarterly 38 (1):293-298.
    It is known that for two given countable sets of unary relations A and B on ω there exists an infinite set H ⫅ ω on which A and B are the same. This result can be used to generate counterexamples in expressibility theory. We examine the sharpness of this result.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  19
    Some Ramsey Theory in Boolean Algebra for Complexity Classes.Gregory L. McColm - 1992 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 38 (1):293-298.
  8.  25
    The Dimension of the Negation of Transitive Closure.Gregory L. McColm - 1995 - Journal of Symbolic Logic 60 (2):392-414.
    We prove that any positive elementary (least fixed point) induction expressing the negation of transitive closure on finite nondirected graphs requires at least two recursion variables.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark