Fly-automata for checking \(\mathrm{MSO}_2\) graph properties

DOI10.1016/j.dam.2016.10.018zbMath1445.03045arXiv1511.08605OpenAlexW2288162826MaRDI QIDQ1752502

Bruno Courcelle

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08605

zbMATH Keywords

monadic second-order logicgraphstree automatabounded tree-width

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Courcelle's theorem -- a game-theoretic approach
• On the model-checking of monadic second-order formulas with edge set quantifications
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• The complexity of first-order and monadic second-order logic revisited
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Model-Checking by Infinite Fly-Automata
• Fly-Automata, Their Properties and Applications
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computations by fly-automata beyond monadic second-order logic