The dimension of the negation of transitive closure
- 1 June 1995
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 60 (2) , 392-414
- https://doi.org/10.2307/2275838
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.Keywords
This publication has 13 references indexed in Scilit:
- Eventual periodicity and ``one-dimensional'' queries.Notre Dame Journal of Formal Logic, 1992
- Parametrization over inductive relations of a bounded number of variablesAnnals of Pure and Applied Logic, 1990
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- A programming language for the inductive sets, and applicationsInformation and Control, 1984
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Application of model theoretic games to discrete linear orders and finite automataInformation and Control, 1977
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- The monadic second order theory of ω1Published by Springer Nature ,1973