Timed languages, dyadic approximations and regular tree grammars
Jean-Franqois Antoniotti, Dominique Luzeaux · 1999
Our research on the modelization of the loop actionperception for an autonomous robot has led us naturally towards a tree-like representation of that interaction: a node is labeled by a perceptive context of the robot, the different branches correspond to the various available actions and the children nodes are then the effect of these different actions on the original context. This tree-like view allows us to state rigorously the problems of viable control in terms of games: the existence of a controller is reduced to the existence of strategies which allow to walk through the trees representing the system in order to remain within a given class of contexts (viability goal). Such game approaches are widely used in computer science (BL69; Mos89; NYY92), and appear in hybrid control theory too (TLS98). Furthermore it is necessary to describe these tree sets as simply as possible, in order to decide for the existence of a controller, and in the best case to synthesize such a controller (The95). In this paper, we study timed automata from the point of view of regular tree grammars showing how our approach can be applied to this central class of decidable hybrid systems.