2026-07-23T00:24:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2332 2024-03-06T10:33:19Z ddc:004 open_access

Synthesis of Finite-state and Definable Winning Strategies Rabinovich, Alexander Games of ordinal length Church Synthesis Problem Monadic Logic Composition Method Church's Problem asks for the construction of a procedure which, given a logical specification $\varphi$ on sequence pairs, realizes for any input sequence $I$ an output sequence $O$ such that $(I,O)$ satisfies $\varphi$. McNaughton reduced Church's Problem to a problem about two-player$\omega$-games. B\"uchi and Landweber gave a solution for Monadic Second-Order Logic of Order ($\MLO$) specifications in terms of finite-state strategies. We consider two natural generalizations of the Church problem to countable ordinals: the first deals with finite-state strategies; the second deals with $\MLO$-definable strategies. We investigate games of arbitrary countable length and prove the computability of these generalizations of Church's problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Rabinovich 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2332 urn:nbn:de:0030-drops-23320 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2332 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode