. "[B78C6012AA9C]" . "Hlin\u011Bn\u00FD, Petr" . . "14330" . "2008-09-13+02:00"^^ . "United Kingdom" . "Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications" . . . . "Rank-width is a rather new structural graph measure introduced by Oum and Seymour in 2003 in order to find an efficiently computable approximation of clique-width of a graph. Being a very nice graph measure indeed, the only serious drawback of rank-width was that it is virtually impossible to use a given rank-decomposition of a graph for running dynamic algorithms on it. We propose a new independent description of rank-decompositions of graphs using labeling parse trees which is, after all, mathematically equivalent to the recent algebraic graph-expression approach to rank-decompositions of Courcelle and Kant\\'e [WG'07]. We then use our labeling parse trees to build a Myhill-Nerode-type formalism for handling restricted classes of graphs of bounded rank-width, and to directly prove that (an already indirectly known result) all graph properties expressible in MSO logic are decidable by finite automata running on the labeling parse trees."@en . . "P(1M0545), P(GA201/08/0308)" . "12"^^ . . . "RIV/00216224:14330/08:00025022" . "Rank-width is a rather new structural graph measure introduced by Oum and Seymour in 2003 in order to find an efficiently computable approximation of clique-width of a graph. Being a very nice graph measure indeed, the only serious drawback of rank-width was that it is virtually impossible to use a given rank-decomposition of a graph for running dynamic algorithms on it. We propose a new independent description of rank-decompositions of graphs using labeling parse trees which is, after all, mathematically equivalent to the recent algebraic graph-expression approach to rank-decompositions of Courcelle and Kant\\'e [WG'07]. We then use our labeling parse trees to build a Myhill-Nerode-type formalism for handling restricted classes of graphs of bounded rank-width, and to directly prove that (an already indirectly known result) all graph properties expressible in MSO logic are decidable by finite automata running on the labeling parse trees." . "Automata Approach to Graphs of Bounded Rank-width" . "Automata Approach to Graphs of Bounded Rank-width"@en . "357363" . . . . "Automata Approach to Graphs of Bounded Rank-width" . . "978-1-904987-74-1" . "International Workshop on Combinatorial Algorithms IWOCA 2008" . "Automata Approach to Graphs of Bounded Rank-width"@en . . "2"^^ . . . . "Ganian, Robert" . "Nagoya, Japan" . . "2"^^ . "RIV/00216224:14330/08:00025022!RIV11-GA0-14330___" . "parameterized algorithm; rank-width; tree automaton; MSO logic"@en . . .