Courcelle, Bruno
Special treewidth and the verification of monadic secondorder graph pr operties
Abstract
The modelchecking problem for monadic secondorder logic on graphs is fixedparameter tractable with respect to treewidth and cliquewidth. The proof constructs finite deterministic automata from monadic secondorder sentences, but this computation produces automata of hyperexponential sizes, and this is not avoidable. To overcome this difficulty, we propose to consider particular monadic secondorder graph properties that are nevertheless interesting for Graph Theory and to interpret automata instead of trying to compile them (joint work with I. Durand).
For checking monadic secondorder sentences written with edge set quantifications, the appropriate parameter is treewidth. We introduce special treewidth, a graph complexity measure between pathwidth and treewidth. The corresponding automata are easier to construct than those for treewidth.
BibTeX  Entry
@InProceedings{courcelle:LIPIcs:2010:2849,
author = {Bruno Courcelle},
title = {{Special treewidth and the verification of monadic secondorder graph pr operties}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {1329},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2849},
URN = {urn:nbn:de:0030drops28494},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.13},
annote = {Keywords: modelchecking, monadic secondorder logic, fixedparameter tractability, special treewidth}
}
2010
Keywords: 

modelchecking, monadic secondorder logic, fixedparameter tractability, special treewidth 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 