The dimension of the negation of transitive closure
From MaRDI portal
Publication:4842619
DOI10.2307/2275838zbMath0826.03015MaRDI QIDQ4842619
Publication date: 28 November 1995
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275838
Related Items
Cites Work
- Parametrization over inductive relations of a bounded number of variables
- Number of quantifiers is better than number of tape cells
- Upper and lower bounds for first order expressibility
- Eventual periodicity and ``one-dimensional queries
- Structure and complexity of relational queries
- Some restrictions on simple fixed points of the integers
- A programming language for the inductive sets, and applications
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Monadic generalized spectra
- Application of model theoretic games to discrete linear orders and finite automata