Solution of Church's Problem: A Tutorial Wolfgang Thomas

Routledge eBooks, pp. 211–236

Abstract

Church&s;s Problem (1957) asks for the construction of a finite-state procedure that transforms any input sequence α letter by letter into an output sequence β such that the pair ( α , β ) satisfies a given specification. Even after the solution by Büchi and Landweber in 1969 (for specifications in monadic second-order logic over the structure (ℕ, +1)), the problem has stimulated research in automata theory for decades, in recent years mainly in the algorithmic study of infinite games. We present a modern solution which proceeds in several stages (each of them of moderate difficulty) and provides additional insight into the structure of the synthesized finite-state transducers.

Authors 1

1. Wolfgang Thomas corresponding Aachen Lehrstuhl Informatik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl Informatik RWTH Aachen University 52074 Aachen , Germany