Displaying similar documents to “ω-Trees in stationary logic”

Choice functions and well-orderings over the infinite binary tree

Arnaud Carayol, Christof Löding, Damian Niwinski, Igor Walukiewicz (2010)

Open Mathematics

Similarity:

We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable...

Galvin Tree-Games

E. C. Milner (1985)

Publications du Département de mathématiques (Lyon)

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.

Diversity of logical agents in games

Johan van Benthem, Fenrong Liu (2004)

Philosophia Scientiae

Similarity:

Epistemic agents may have different powers of observation and reasoning, and we show how this diversity fits into dynamic update logics.

Club-guessing and non-structure of trees

Tapani Hyttinen (2001)

Fundamenta Mathematicae

Similarity:

We study the possibilities of constructing, in ZFC without any additional assumptions, strongly equivalent non-isomorphic trees of regular power. For example, we show that there are non-isomorphic trees of power ω₂ and of height ω · ω such that for all α < ω₁· ω · ω, E has a winning strategy in the Ehrenfeucht-Fraïssé game of length α. The main tool is the notion of a club-guessing sequence.