Synthesis of Finite-state and Definable Winning Strategies

Rabinovich, Alexander

doi:10.4230/LIPIcs.FSTTCS.2009.2332

Document

Synthesis of Finite-state and Definable Winning Strategies

Author Alexander Rabinovich

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: 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

PDF

File

PDF

LIPIcs.FSTTCS.2009.2332.pdf

Filesize: 126 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2009.2332
URN: urn:nbn:de:0030-drops-23320

Subject Classification

Keywords

Games of ordinal length
Church Synthesis Problem
Monadic Logic
Composition Method

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

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

Author Details

Alexander Rabinovich

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail