Premium
Dimension Versus Number of Variables, and Connectivity, too
Author(s) -
McColm Gregory L.
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410110
Subject(s) - mathematics , dimension (graph theory) , point (geometry) , variable (mathematics) , combinatorics , discrete mathematics , statistics , mathematical analysis , geometry
We present game‐theoretic characterizations of the complexity/expressibility measures “dimension” and “the number of variables” as Least Fixed Point queries. As an example, we use these characterizations to compute the dimension and number of variables of Connectivity and Connectivity.