Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T18:09:13.000Z Has data issue: false hasContentIssue false

Church's Problem Revisited

Published online by Cambridge University Press:  15 January 2014

Orna Kupferman
Affiliation:
The Institute of Computer Science, Hebrew University, Jerusalem 91904, ISRAEL E-mail: orna@cs.huji.ac.il
Moshe Y. Vardi
Affiliation:
Department Of Computer Science, Rice University, Houston, TEXAS 77005-1892, USA E-mail: vardi@cs.rice.edu

Abstract

In program synthesis, we transform a specification into a system that is guaranteed to satisfy the specification. When the system is open, then at each moment it reads input signals and writes output signals, which depend on the input signals and the history of the computation so far. The specification considers all possible input sequences. Thus, if the specification is linear, it should hold in every computation generated by the interaction, and if the specification is branching, it should hold in the tree that embodies all possible input sequences.

Often, the system cannot read all the input signals generated by its environment. For example, in a distributed setting, it might be that each process can read input signals of only part of the underlying processes. Then, we should transform a specification into a system whose output depends only on the readable parts of the input signals and the history of the computation. This is called synthesis with incomplete information. In this work we solve the problem of synthesis with incomplete information in its full generality. We consider linear and branching settings with complete and incomplete information. We claim that alternation is a suitable and helpful mechanism for coping with incomplete information. Using alternating tree automata, we show that incomplete information does not make the synthesis problem more complex, in both the linear and the branching paradigm. In particular, we prove that independently of the presence of incomplete information, the synthesis problems for CTL and CTL*. are complete for EXPTIME and 2EXPTIME, respectively.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable