Appears in collection : Frontiers of reconnaissability / Frontières de la reconnaissabilité

In order to be interesting, algebras of finite graphs must have countable sets of operations. We adapt accordingly the notion of recognizability, defined usually for finitely generated algebras. We prove the recognizability theorem, saying that monadic second-order definable sets of graphs are recognizable, by means of infinite "fly-automata". These automata can be implemented and used for obtaining FPT algorithms with respect to clique-width or tree-width as parameter. The implementation issues will be exposed by I. Durand.