Dimension Versus Number of Variables, and Connectivity, too

Mathematical Logic Quarterly 41 (1):111-134 (1995)
  Copy   BIBTEX

Abstract

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

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.19950410110

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,907

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The dimension of the negation of transitive closure.Gregory L. McColm - 1995 - Journal of Symbolic Logic 60 (2):392-414.
Guarded quantification in least fixed point logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.
Common knowledge logic and game logic.Mamoru Kaneko - 1999 - Journal of Symbolic Logic 64 (2):685-700.
Acting in concert or going it alone: Game theory and the law.Theodore M. Benditt - 2004 - Law and Philosophy 23 (6):615 - 630.
Game logic is strong enough for parity games.Dietmar Berwanger - 2003 - Studia Logica 75 (2):205 - 219.
Axiomatizations of a Class of Equal Surplus Sharing Solutions for TU-Games.René van den Brink & Yukihiko Funaki - 2009 - Theory and Decision 67 (3):303-340.
A Relationship Among Gentzen's Proof‐Reduction, Kirby‐Paris' Hydra Game and Buchholz's Hydra Game.Masahiro Hamano & Mitsuhiro Okada - 1997 - Mathematical Logic Quarterly 43 (1):103-120.
Transition semantics: the dynamics of dependence logic.P. Galliani - 2014 - Synthese 191 (6):1249-1276.
Games as formal tools versus games as explanations in logic and science.Ahti-Veikko Pietarinen - 2003 - Foundations of Science 8 (4):317-364.
A guarded fragment for abstract state machines.Antje Nowack - 2005 - Journal of Logic, Language and Information 14 (3):345-368.
Determined game logic is complete.Jan van Eijck - unknown

Analytics

Added to PP
2013-12-01

Downloads
10 (#1,217,101)

6 months
7 (#486,337)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Guarded quantification in least fixed point logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.
The dimension of the negation of transitive closure.Gregory L. McColm - 1995 - Journal of Symbolic Logic 60 (2):392-414.

Add more citations

References found in this work

Descriptive Set Theory.Richard Mansfield - 1981 - Journal of Symbolic Logic 46 (4):874-876.
Descriptive Set Theory.Yiannis Nicholas Moschovakis - 1982 - Studia Logica 41 (4):429-430.
Elementary Induction on Abstract Structures.Wayne Richter - 1979 - Journal of Symbolic Logic 44 (1):124-125.

Add more references