Displaying similar documents to “Limit probabilities for random sparse bit strings.”

Fixpoints, games and the difference hierarchy

Julian C. Bradfield (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over Σ 2 0 . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.

Three notes on the complexity of model checking fixpoint logic with chop

Martin Lange (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal -calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity...

The game of End-Nim.

Albert, Michael H., Nowakowski, Richard J. (2001)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On independence-friendly fixpoint logics

J. C. Bradfield (2004)

Philosophia Scientiae

Similarity:

We introduce a fixpoint extension of Hintikka and Sandu’s IF (independence-friendly) logic. We obtain some results on its complexity and expressive power. We relate it to parity games of imperfect information, and show its application to defining independence-friendly modal mu-calculi.