The dimension of the negation of transitive closure

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


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



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

External links

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

Through your library


Added to PP

30 (#534,905)

6 months
5 (#645,438)

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