Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
type: Item
instance of: scholarly article
title: Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
zbMATH Open document ID: 1347.03077
publication date: 2016-10-17T00:00:00Z
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 03B15
zbMATH DE Number: 6639861
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: tree-width
zbMATH Keywords: incidence graph
zbMATH Keywords: clique-width
zbMATH Keywords: fly-automaton
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: edge quantification
zbMATH Keywords: model checking
MaRDI profile type: Publication
full work available at URL: j.endm.2015.07.002
OpenAlex ID: W2212883086
cites work: On the model-checking of monadic second-order formulas with edge set quantifications
cites work: Automata for the verification of monadic second-order graph properties
cites work: Model-Checking by Infinite Fly-Automata
cites work: Q3077955
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Q4393480
cites work: The complexity of first-order and monadic second-order logic revisited
DOI: 10.1016/J.ENDM.2015.07.002
author: Bruno Courcelle
Recommended article: Automata for the verification of monadic second-order graph properties
Recommended article: Special tree-width and the verification of monadic second-order graph properties
Recommended article: Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
Recommended article: Computations by fly-automata beyond monadic second-order logic
Recommended article: Monadic Second Order Finite Satisfiability and Unbounded Tree-Width
Recommended article: The monadic second-order logic of graphs, II: Infinite graphs of bounded width
Recommended article: Q4381404
Recommended article: Verifying Monadic Second-Order Properties of Graph Programs
Recommended article: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
description: scientific article; zbMATH DE number 6639861