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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom