Synthesis of Discrete Reactive Systems


Paul Hänsch

Title Synthesis of Discrete Reactive Systems
When 02.07.2009
Where Lecture Room Informatik 7
Abstract We study an extension of the synthesis problem based on regular games, better known as Church’s Synthesis Problem. We consider regular P-games, i.e. regular games with an additional predicate P and reprove a known result of Rabinovich on the solvability of the corresponding synthesis problem. We further show for a broad class of predicates P that the induced regular P-games allow winning strategies of a particularly simple shape, i.e. realizable by higher-order pushdown automata (with tests). Those are the predicates P for which (N,<,P) belongs to the Caucal Hierarchy.This talk is part of an application for a scholarship in the AlgoSyn programme.