Graph structure and monadic second-order logic. A language-theoretic approach

zbMATH Open1257.68006MaRDI QIDQ3077955FDOQ3077955

Authors: Joost Engelfriet, Bruno Courcelle

Publication date: 18 February 2011

Recommendations

Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
scientific article; zbMATH DE number 1696755
scientific article; zbMATH DE number 177437
The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

graph algorithms finite graphs formal languages monadic second-order logic

Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Cited In (only showing first 100 items - show all)

Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
Practical algorithms for MSO model-checking on tree-decomposable graphs
A regular characterization of graph languages definable in monadic second-order logic
Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
The monadic second-order logic of graphs. VII: Graphs as relational structures
Recurrence relations for graph polynomials on bi-iterative families of graphs
A Retrospective on (Meta) Kernelization
Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
An algorithmic metatheorem for directed treewidth
Clique-width of path powers
Acyclic coloring parameterized by directed clique-width
Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
Are there any good digraph width measures?
The complexity of two graph orientation problems
Title not available (Why is that?)
The monadic second-order logic of graphs XVI : Canonical graph decompositions
Courcelle's theorem -- a game-theoretic approach
A linear time algorithm for metric dimension of cactus block graphs
A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
Deleting edges to restrict the size of an epidemic in temporal networks
Deleting edges to restrict the size of an epidemic in temporal networks
Graph planning with expected finite horizon
Algebras for tree decomposable graphs
On the computational complexity of the bipartizing matching problem
FPT and kernelization algorithms for the induced tree problem
Network-based vertex dissolution
Analyzing timed systems using tree automata
A logical approach to locality in pictures languages
Clique-width and edge contraction
Determinacy and rewriting of functional top-down and MSO tree transformations
Linear rank-width and linear clique-width of trees
Comparing linear width parameters for directed graphs
Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
Fast exact algorithms for some connectivity problems parameterized by clique-width
On the tree-width of even-hole-free graphs
Automata for the verification of monadic second-order graph properties
Two-way pebble transducers for partial functions and their composition
Recognizability equals definability for graphs of bounded treewidth and bounded chordality
Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
Roman domination in subgraphs of grids
A characterisation of clique-width through nested partitions
From tree-decompositions to clique-width terms
Title not available (Why is that?)
Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
Finding a subdivision of a digraph
Computations by fly-automata beyond monadic second-order logic
The enumeration of vertex induced subgraphs with respect to the number of components
Faster Property Testers in a Variation of the Bounded Degree Model
Partial complementation of graphs
Courcelle's theorem for triangulations
How to compute digraph width measures on directed co-graphs
Computing square roots of graphs with low maximum degree
Monadic second-order logic, graph coverings and unfoldings of transition systems
Contextual hyperedge replacement
On the parameterized complexity of non-monotonic logics
Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
Large Induced Subgraphs via Triangulations and CMSO
Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
Second-order propositional modal logic: expressiveness and completeness results
XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
The monadic quantifier alternation hierarchy over grids and graphs
Clique-perfectness of complements of line graphs
Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
The rank-width of edge-coloured graphs
Several notions of rank-width for countable graphs
Fly-automata, their properties and applications
On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
Towards an Efficient Tree Automata based technique for Timed Systems
Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
Title not available (Why is that?)
The behavior of clique-width under graph operations and graph transformations
A new approach for contact graph representations and its applications
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
The monadic second-order logic of graphs. IX: Machines and their behaviours
Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
Logics for unordered trees with data constraints
On retracts, absolute retracts, and foldings in cographs
Finer tight bounds for coloring on clique-width
Finer tight bounds for coloring on clique-width
Existential monadic second order logic on random rooted trees
Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
Treewidth-two graphs as a free algebra
Finding a potential community in networks
Reachability analysis of reversal-bounded automata on series-parallel graphs
Shelah-Stupp's and Muchnik's iterations revisited
Harary polynomials
Rabin's theorem in the concurrency setting: a conjecture
Multiple context-free tree grammars: lexicalization and characterization
Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
Parameterized model checking of rendezvous systems
A Decision Procedure for Guarded Separation Logic Complete Entailment Checking for Separation Logic with Inductive Definitions
Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
Betweenness of partial orders
Property testing for bounded degree databases
Regular model checking with regular relations
Verification of agent navigation in partially-known environments
Tractability, hardness, and kernelization lower bound for and/or graph solution
Properties of graphs specified by a regular language
On caterpillar factors in graphs

Uses Software

Autowrite
MONA

This page was built for publication: Graph structure and monadic second-order logic. A language-theoretic approach

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