Automata Approach to Graphs of Bounded Rank-width

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00025022" target="_blank" >RIV/00216224:14330/08:00025022 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Automata Approach to Graphs of Bounded Rank-width

Popis výsledku v původním jazyce

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-widthwas 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.

Název v anglickém jazyce

Automata Approach to Graphs of Bounded Rank-width

Popis výsledku anglicky

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-widthwas 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

International Workshop on Combinatorial Algorithms IWOCA 2008

ISBN

978-1-904987-74-1

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications

Místo vydání

United Kingdom

Místo konání akce

Nagoya, Japan

Datum konání akce

13. 9. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—