Publication:3077955
From MaRDI portal
zbMath1257.68006MaRDI QIDQ3077955
Bruno Courcelle, Joost Engelfriet
Publication date: 18 February 2011
05C90: Applications of graph theory
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
03D05: Automata and formal grammars in connection with logical questions
68-02: Research exposition (monographs, survey articles) pertaining to computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Unnamed Item, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Recognizable languages of arrows and cospans, Beyond Outerplanarity, Model checking existential logic on partially ordered sets, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Betweenness of partial orders, Induced betweenness in order-theoretic trees, Order-theoretic Trees: Monadic Second-order Descriptions and Regularity, On the Tutte and Matching Polynomials for Complete Graphs, As Time Goes By: Reflections on Treewidth for Temporal Graphs, A Retrospective on (Meta) Kernelization, Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs, Betweenness in Order-Theoretic Trees, Harary polynomials, Convolution and concurrency, Generating Posets Beyond N, Algebras for Tree Decomposable Graphs, Finer Tight Bounds for Coloring on Clique-Width, Bundled Crossings Revisited, Reducing CMSO model checking to highly connected graphs, Acyclic polynomials of graphs, Fly-Automata, Their Properties and Applications, Where First-Order and Monadic Second-Order Logic Coincide, Origin-equivalence of two-way word transducers is in PSPACE, On Synthesis of Resynchronizers for Transducers, Towards an Efficient Tree Automata based technique for Timed Systems, Partial complementation of graphs, Network-Based Vertex Dissolution, Parametrised Complexity of Satisfiability in Temporal Logic, Unnamed Item, Unnamed Item, Properties of graphs specified by a regular language, Properties of graphs specified by a regular language, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, On \(H\)-topological intersection graphs, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs, Computing with Tangles, Computations by fly-automata beyond monadic second-order logic, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, Streaming ranked-tree-to-string transducers, The Parameterized Complexity of Graph Cyclability, Feedback edge sets in temporal graphs, Clique-width of point configurations, Clique-perfectness of complements of line graphs, A Decision Procedure for Guarded Separation Logic Complete Entailment Checking for Separation Logic with Inductive Definitions, Towards compositional graph theory, On the parameterized complexity of the acyclic matching problem, Seurat games on Stockmeyer graphs, Grouped domination parameterized by vertex cover, twin cover, and beyond, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Clique‐width: Harnessing the power of atoms, On the algebraization of Henkin‐type second‐order logic, Unfoldings and Coverings of Weighted Graphs, Grouped domination parameterized by vertex cover, twin cover, and beyond, Faster Property Testers in a Variation of the Bounded Degree Model, Edge deletion to tree-like graph classes, Computing the best-case energy complexity of satisfying assignments in monotone circuits, On the computational complexity of the bipartizing matching problem, Parameterized complexity of computing maximum minimal blocking and hitting sets, FPT and kernelization algorithms for the induced tree problem, Perfectly matched sets in graphs: parameterized and exact computation, Parameterized Complexity of CTL, Verification of Parameterized Communicating Automata via Split-Width, Strong Backdoors for Default Logic, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, Causality in Bounded Petri Nets is MSO Definable, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Myhill-Nerode Methods for Hypergraphs, Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus, Regularity Equals Monadic Second-Order Definability for Quasi-trees, Capturing MSO with One Quantifier, Large Induced Subgraphs via Triangulations and CMSO, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Unified Reasoning About Robustness Properties of Symbolic-Heap Separation Logic, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections, Digraphs of Bounded Width, Graph Transformation Meets Reversible Circuits: Model Transformation and Optimization, Unnamed Item, A New Approach for Contact Graph Representations and Its Applications, Property Testing for Bounded Degree Databases, An algorithmic metatheorem for directed treewidth, Clique-width of path powers, A linear time algorithm for metric dimension of cactus block graphs, A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs, A logical approach to locality in pictures languages, 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, Courcelle's theorem for triangulations, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Courcelle's theorem -- a game-theoretic approach, The complexity of two graph orientation problems, Well-quasi-ordering of matrices under Schur complement and applications to directed graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Finding a subdivision of a digraph, Contextual hyperedge replacement, On the parameterized complexity of non-monotonic logics, Several notions of rank-width for countable graphs, The behavior of clique-width under graph operations and graph transformations, The enumeration of vertex induced subgraphs with respect to the number of components, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Determinacy and rewriting of functional top-down and MSO tree transformations, Recurrence relations for graph polynomials on bi-iterative families of graphs, Two-way pebble transducers for partial functions and their composition, Acyclic coloring parameterized by directed clique-width, Are there any good digraph width measures?, Meta-kernelization with structural parameters, The generative power of delegation networks, Existential monadic second order logic on random rooted trees, Parameterized model checking of rendezvous systems, Balancedness of MSO transductions in polynomial time, 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, Second-order propositional modal logic: expressiveness and completeness results, Finding a potential community in networks, Reachability analysis of reversal-bounded automata on series-parallel graphs, Multiple context-free tree grammars: lexicalization and characterization, On retracts, absolute retracts, and foldings in cographs, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Fly-automata for checking \(\mathrm{MSO}_2\) graph properties, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Automata for the verification of monadic second-order graph properties, On the tree-width of even-hole-free graphs, The complexity of finding small separators in temporal graphs, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, Measuring what matters: a hybrid approach to dynamic programming with treewidth, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, Context-sensitive fusion grammars and fusion grammars with forbidden context are universal, Maximum matching in almost linear time on graphs of bounded clique-width, A meta-theorem for distributed certification, ASNP: a tame fragment of existential second-order logic, Shelah-Stupp's and Muchnik's iterations revisited, Verifying graph programs with monadic second-order logic, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Regular model checking with regular relations, Verification of agent navigation in partially-known environments, Minimum \(t\)-spanners on subcubic graphs, A general framework for path convexities, An adjacency labeling scheme based on a decomposition of trees into caterpillars, Grammars and clique-width bounds from split decompositions, On quasi-planar graphs: clique-width and logical description, Subgraph complementation, Parameterized orientable deletion, Bisimulation invariant monadic-second order logic in the finite, Bundled crossings revisited, Graph theory in Coq: minors, treewidth, and isomorphisms, On caterpillar factors in graphs, XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles, How to compute digraph width measures on directed co-graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, One-way resynchronizability of word transducers, Efficient computation of the oriented chromatic number of recursively defined digraphs, Rabin's theorem in the concurrency setting: a conjecture, Language theoretic properties of regular DAG languages, Nontrivial path covers of graphs: existence, minimization and maximization, On width measures and topological problems on semi-complete digraphs, Comparing linear width parameters for directed graphs, Linear rank-width and linear clique-width of trees, On labeled birooted tree languages: algebras, automata and logic, A characterisation of clique-width through nested partitions, Clique-width and edge contraction, The rank-width of edge-coloured graphs, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Tractability, hardness, and kernelization lower bound for and/or graph solution, Parameterized edge Hamiltonicity, Computing square roots of graphs with low maximum degree, From tree-decompositions to clique-width terms, Fast exact algorithms for some connectivity problems parameterized by clique-width, Specifying graph languages with type graphs, Logics for unordered trees with data constraints, Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries, Computability by monadic second-order logic, Deleting edges to restrict the size of an epidemic in temporal networks, Posets with interfaces as a model for concurrency, FPT algorithms to compute the elimination distance to bipartite graphs and more, Transformation of variants of Petri nets into context-dependent fusion grammars, The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic, Graph planning with expected finite horizon, Unnamed Item, A meta-theorem for distributed certification, On the parameterized complexity of s-club cluster deletion problems, Tree automata and pigeonhole classes of matroids. II, Extended MSO model checking via small vertex integrity, Some new algorithmic results on co-secure domination in graphs, Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
Uses Software
