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)

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
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
Parameterized orientable deletion
Parameterized orientable deletion
Title not available (Why is that?)
Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
On the computational complexity of variants of combinatorial voter control in elections
Computability by monadic second-order logic
On width measures and topological problems on semi-complete digraphs
Minimum \(t\)-spanners on subcubic graphs
Nontrivial path covers of graphs: existence, minimization and maximization
Bundled crossings revisited
Measuring what matters: a hybrid approach to dynamic programming with treewidth
FPT algorithms to compute the elimination distance to bipartite graphs and more
Beyond outerplanarity
Maximum matching in almost linear time on graphs of bounded clique-width
Title not available (Why is that?)
Reducing CMSO model checking to highly connected graphs
Meta-kernelization with structural parameters
The generative power of delegation networks
An adjacency labeling scheme based on a decomposition of trees into caterpillars
Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
Betweenness in order-theoretic trees
Acyclic polynomials of graphs
On the Tutte and Matching Polynomials for Complete Graphs
Title not available (Why is that?)
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
On labeled birooted tree languages: algebras, automata and logic
On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
Prefix-Recognizable Graphs and Monadic Logic
Balancedness of MSO transductions in polynomial time
Digraphs of bounded width
Induced betweenness in order-theoretic trees
Subgraph complementation
The complexity of finding small separators in temporal graphs
A meta-theorem for distributed certification
ASNP: a tame fragment of existential second-order logic
Verifying graph programs with monadic second-order logic
Parametrised complexity of satisfiability in temporal logic
Unified reasoning about robustness properties of symbolic-heap separation logic
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

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)