Alexander Rabinovich - The Church Problem for Countable Ordinals

lmcs:1204 - Logical Methods in Computer Science, April 27, 2009, Volume 5, Issue 2 - https://doi.org/10.2168/LMCS-5(2:5)2009
The Church Problem for Countable OrdinalsArticle

Authors: Alexander Rabinovich

    A fundamental theorem of Buchi and Landweber shows that the Church synthesis problem is computable. Buchi and Landweber reduced the Church Problem to problems about &#969;-games and used the determinacy of such games as one of the main tools to show its computability. We consider a natural generalization of the Church problem to countable ordinals and investigate games of arbitrary countable length. We prove that determinacy and decidability parts of the Bu}chi and Landweber theorem hold for all countable ordinals and that its full extension holds for all ordinals < \omega\^\omega.


    Volume: Volume 5, Issue 2
    Published on: April 27, 2009
    Imported on: October 27, 2007
    Keywords: Computer Science - Logic in Computer Science,F.4.1

    Consultation statistics

    This page has been seen 908 times.
    This article's PDF has been downloaded 222 times.