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

DOI10.4230/LIPICS.FSTTCS.2010.13MaRDI QIDQ2908834zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 29 August 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_697d.html

zbMATH Keywords

fixed-parameter tractabilitymodel-checkingmonadic second-order logicspecial tree-width

Mathematics Subject Classification ID

Logic in computer science (03B70) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the model-checking of monadic second-order formulas with edge set quantifications
• Automata for the verification of monadic second-order graph properties
• On the parameterized intractability of monadic second-order logic
• On the Parameterised Intractability of Monadic Second-Order Logic
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width

Cited in

(7)

• Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
• Automata for the verification of monadic second-order graph properties
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
• Courcelle's theorem -- a game-theoretic approach
• On the model-checking of monadic second-order formulas with edge set quantifications
• Analyzing timed systems using tree automata
• Practical algorithms for MSO model-checking on tree-decomposable graphs

Describes a project that uses

Uses Software

• Autowrite

This page was built for publication: Special tree-width and the verification of monadic second-order graph properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908834)