Wykład Alexandra Rabinovicha

Szanowni Panstwo,

seredcznie zapraszam na wyklad

  Alexander Rabinovich (Tel Aviv University)

  A Survey of Selection and Uniformization Problems

  Sroda, 3.09, godz. 14:00--15:30, s. 5060

Ponizej autorskie strszczenie wykladu.

Profesor Rabinovich bedzie gosciem Instytutu Informatyki
w dniach 1.09--13.09.

Damian Niwinski

====================================================================
A Survey of Selection and Uniformization Problems

A formula ?(Y ) is a selector for a formula F(Y ) in a structure
M if there exists a unique Y that satisfies ? in M and this Y also
satisfies F. A formula ?(X, Y ) uniformizes a formula F(X, Y ) in a structure
M if for every X there exists a unique Y such that ?(X, Y ) holds
in M and for this Y , F(X, Y ) also holds in M. In this paper we survey
some fundamental algorithmic questions and recent results regarding selection
and uniformization, when the formulas ? and F are formulas of
the monadic logic of order and the structure M= (?,<) is an ordinal ?
equipped with its natural order. A natural generalization of the Church
problem to ordinals is obtained when some additional requirements are
imposed on the uniformizing formula ?(X, Y ).We present what is known
regarding this generalization of Church?s problem.
=====================================================================