The Dimension of the Negation of Transitive Closure
McColm, Gregory L.
J. Symbolic Logic, Tome 60 (1995) no. 1, p. 392-414 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 1995-06-14
Classification:  Finite model theory,  computational expressibility,  pebble games,  transitive closure,  connectivity,  fixedpoint logic,  number of variables 
@article{1183744743,
     author = {McColm, Gregory L.},
     title = {The Dimension of the Negation of Transitive Closure},
     journal = {J. Symbolic Logic},
     volume = {60},
     number = {1},
     year = {1995},
     pages = { 392-414},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744743}
}

McColm, Gregory L. The Dimension of the Negation of Transitive Closure. J. Symbolic Logic, Tome 60 (1995) no. 1, pp.  392-414. http://gdmltest.u-ga.fr/item/1183744743/