The dimension of the negation of transitive closure

DOI10.2307/2275838zbMath0826.03015OpenAlexW2077606875MaRDI QIDQ4842619

Gregory Loren McColm

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

zbMATH Keywords

fixed point logictransitive closurefinite model theory

Mathematics Subject Classification ID

Database theory (68P15) Model theory of finite structures (03C13) Other applications of logic (03B80)

Related Items (1)

Dimension Versus Number of Variables, and Connectivity, too

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

This page was built for publication: The dimension of the negation of transitive closure