Fly-automata for checking monadic second-order properties of graphs of bounded tree-width.

Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables ); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width . An MSO property with edge quantifications (called an MSO 2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO 2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation. [ABSTRACT FROM AUTHOR]