Dimension Versus Number of Variables, and Connectivity, too

DOI10.1002/malq.19950410110zbMath0817.03015OpenAlexW2130699742MaRDI QIDQ4323836

Gregory Loren McColm

Publication date: 27 July 1995

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19950410110

zbMATH Keywords

comparison gamepebble gameleast fixed point logic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40) Other infinitary logic (03C75) Other applications of logic (03B80)

Cites Work

• Elementary induction on abstract structures
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• The dimension of the negation of transitive closure

This page was built for publication: Dimension Versus Number of Variables, and Connectivity, too