Automata for the verification of monadic second-order graph properties
type: Item
instance of: scholarly article
title: Automata for the verification of monadic second-order graph properties
zbMATH Open document ID: 1285.03049
author: Irène Durand
author: Bruno Courcelle
published in: Journal of Applied Logic
publication date: 2013-05-02T00:00:00Z
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6160216
zbMATH Keywords: graph algorithm
zbMATH Keywords: automaton
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: clique-width
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: fly-automaton
describes a project that uses: MONA
describes a project that uses: Autowrite
MaRDI profile type: Publication
full work available at URL: j.jal.2011.07.001
OpenAlex ID: W2020861083
cites work: \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
cites work: Recognizing Berge graphs
cites work: The strong perfect graph theorem
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: On the model-checking of monadic second-order formulas with edge set quantifications
cites work: Q3077955
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Q4393480
cites work: \texttt{Autowrite}: a tool for term rewrite systems and tree automata
cites work: Clique-Width is NP-Complete
cites work: The number of registers required for evaluating arithmetic expressions
cites work: Parametrized complexity theory.
cites work: The complexity of first-order and monadic second-order logic revisited
cites work: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
cites work: Better algorithms for satisfiability problems for formulas of bounded rank-width
cites work: Q4179852
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Monadic datalog over finite structures of bounded treewidth
cites work: Finding Branch-Decompositions and Rank-Decompositions
cites work: $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs
cites work: Approximating clique-width and branch-width
cites work: MSOL partitioning problems on graphs of bounded treewidth and clique-width
cites work: The Complexity of Translating Logic to Finite Automata
cites work: The Generation of Optimal Code for Arithmetic Expressions
cites work: Cosmological lower bound on the circuit complexity of a small problem in logic
DOI: 10.1016/J.JAL.2011.07.001
description: scientific article; zbMATH DE number 6160216