Special tree-width and the verification of monadic second-order graph pr operties

Bruno Courcelle
The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite deterministic automata from monadic second-order sentences, but this computation produces automata of hyper-exponential sizes, and this is not avoidable. To overcome this difficulty, we propose to consider particular monadic second-order graph properties that are nevertheless interesting for Graph Theory and to interpret automata instead of trying to compile them (joint work with I....
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.