The dimension of the negation of transitive closure

Journal of Symbolic Logic 60 (2):392-414 (1995)
  Copy   BIBTEX

Abstract

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

Categories

Keywords

Reprint years

DOI

10.2307/2275838

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,283

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Defining (reflexive) transitive closure on finite models.Jan van Eijck - unknown
-Compatible Transitive Extensions of System CT Logique et Analyse.Lorenzo Peña - unknown
Limits and Strengths of Predicate Logic (and its Alloy Implementation).Jan van Eijck - unknown
On modal μ-calculus and non-well-founded set theory.Luca Alberucci & Vincenzo Salipante - 2004 - Journal of Philosophical Logic 33 (4):343-360.
Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
On best transitive approximations to simple graphs.Leon Horsten - unknown
Disjunctions in closure spaces.Andrzej W. Jankowski - 1985 - Studia Logica 44 (1):11 - 24.

Analytics

Added to PP
2009-01-28

Downloads
30 (#536,225)

6 months
5 (#648,018)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Monadic generalized spectra.Ronald Fagin - 1975 - Mathematical Logic Quarterly 21 (1):89-96.
Dimension Versus Number of Variables, and Connectivity, too.Gregory L. McColm - 1995 - Mathematical Logic Quarterly 41 (1):111-134.
Eventual periodicity and "one-dimensional" queries.Gregory L. McColm - 1992 - Notre Dame Journal of Formal Logic 33 (2):273-290.

Add more references