scientific article
From MaRDI portal
Publication:3077955
zbMath1257.68006MaRDI QIDQ3077955
Bruno Courcelle, Joost Engelfriet
Publication date: 18 February 2011
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (only showing first 100 items - show all)
An algorithmic metatheorem for directed treewidth ⋮ Clique-width of path powers ⋮ Existential monadic second order logic on random rooted trees ⋮ A linear time algorithm for metric dimension of cactus block graphs ⋮ A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs ⋮ Acyclic coloring parameterized by directed clique-width ⋮ A logical approach to locality in pictures languages ⋮ Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids ⋮ Regular model checking with regular relations ⋮ Parameterized model checking of rendezvous systems ⋮ Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries ⋮ Verification of agent navigation in partially-known environments ⋮ 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 ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ A general framework for path convexities ⋮ The rank-width of edge-coloured graphs ⋮ Courcelle's theorem for triangulations ⋮ Computability by monadic second-order logic ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Subgraph complementation ⋮ Parameterized orientable deletion ⋮ Bisimulation invariant monadic-second order logic in the finite ⋮ Parameterized edge Hamiltonicity ⋮ Computing square roots of graphs with low maximum degree ⋮ From tree-decompositions to clique-width terms ⋮ 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 ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Are there any good digraph width measures? ⋮ Meta-kernelization with structural parameters ⋮ Specifying graph languages with type graphs ⋮ The complexity of two graph orientation problems ⋮ The generative power of delegation networks ⋮ Logics for unordered trees with data constraints ⋮ Automata for the verification of monadic second-order graph properties ⋮ Balancedness of MSO transductions in polynomial time ⋮ Bundled crossings revisited ⋮ Graph theory in Coq: minors, treewidth, and isomorphisms ⋮ On caterpillar factors in graphs ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ 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 ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Finding a subdivision of a digraph ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ 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 ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ One-way resynchronizability of word transducers ⋮ Finding a potential community in networks ⋮ Contextual hyperedge replacement ⋮ On the parameterized complexity of non-monotonic logics ⋮ On the tree-width of even-hole-free graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Reachability analysis of reversal-bounded automata on series-parallel graphs ⋮ Several notions of rank-width for countable 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 ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Fly-automata for checking \(\mathrm{MSO}_2\) graph properties ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ The complexity of finding small separators in temporal graphs ⋮ Language theoretic properties of regular DAG languages ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ Recurrence relations for graph polynomials on bi-iterative families of graphs ⋮ Two-way pebble transducers for partial functions and their composition ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Comparing linear width parameters for directed graphs ⋮ 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 ⋮ Linear rank-width and linear clique-width of trees ⋮ ASNP: a tame fragment of existential second-order logic ⋮ On labeled birooted tree languages: algebras, automata and logic ⋮ A characterisation of clique-width through nested partitions ⋮ Clique-width and edge contraction ⋮ Shelah-Stupp's and Muchnik's iterations revisited ⋮ Verifying graph programs with monadic second-order logic
Uses Software
This page was built for publication:
