LIPIcs.FSTTCS.2009.2332.pdf
- Filesize: 126 kB
- 12 pages
Document
Synthesis of Finite-state and Definable Winning Strategies
Author
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-12-14
Cite As Get BibTex
Alexander Rabinovich. Synthesis of Finite-state and Definable Winning Strategies. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 359-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2332
Abstract
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.
Subject Classification
Keywords
- Games of ordinal length
- Church Synthesis Problem
- Monadic Logic
- Composition Method
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads