Handle-rewriting hypergraph grammars

DOI10.1016/0022-0000(93)90004-GzbMath0825.68446OpenAlexW1994887153MaRDI QIDQ2366278

Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg

Publication date: 29 June 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90004-g

Mathematics Subject Classification ID

Hypergraphs (05C65) Grammars and rewriting systems (68Q42)

Related Items (only showing first 100 items - show all)

Monadic second-order definable graph transductions: a survey ⋮ Node replacements in embedding normal form. ⋮ Clique-width of path powers ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ Automatic graphs and D0L-sequences of finite graphs ⋮ The parametrized complexity of knot polynomials ⋮ Tree-depth and vertex-minors ⋮ Eigenvalue location in graphs of small clique-width ⋮ Structural parameterizations of clique coloring ⋮ On coloring a class of claw-free graphs. ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The bounded degree problem for eNCE graph grammars ⋮ The rank-width of edge-coloured graphs ⋮ Algorithms for some graph theoretical optimization problems (abstract of thesis) ⋮ Deciding atomicity of subword-closed languages ⋮ Boundary classes for graph problems involving non-local properties ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Rank-width: algorithmic and structural results ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Well-quasi-order of relabel functions ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Logical description of context-free graph languages ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Infinitely many minimal classes of graphs of unbounded clique-width ⋮ On the thinness and proper thinness of a graph ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Graph classes with and without powers of bounded clique-width ⋮ Independent domination in finitely defined classes of graphs ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Graphs of separability at most 2 ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ Stability number of bull- and chair-free graphs revisited ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ New plain-exponential time classes for graph homomorphism ⋮ Distance labeling scheme and split decomposition ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ Clique-width of partner-limited graphs ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ On prime inductive classes of graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Graph grammars with string-regulated rewriting ⋮ Clique-width with an inactive label ⋮ (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization. ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ Upper bounds to the clique width of graphs ⋮ Order independent NCE grammars recognized in polynomial time ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Computing the clique-width of cactus graphs ⋮ Solving some NP-complete problems using split decomposition ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ Well-quasi-ordering versus clique-width ⋮ A new graph construction of unbounded clique-width ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Recent developments on graphs of bounded clique-width ⋮ On the structure of (\(P_{5}\),\,gem)-free graphs ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Distance-hereditary graphs are clique-perfect ⋮ Finite graph automata for linear and boundary graph languages ⋮ Split permutation graphs ⋮ Recognizability, hypergraph operations, and logical types ⋮ Boolean-width of graphs ⋮ Graphs of linear clique-width at most 3 ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ Structure and stability number of chair-, co-P- and gem-free graphs revisited ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Nondeterministic operations on finite relational structures ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Generating irregular partitionable data structures ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Double Greibach operator grammars ⋮ Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. ⋮ Clique-width of full bubble model graphs ⋮ The complexity of the \(K_{n,n}\)-problem for node replacement graph languages ⋮ Node replacement graph grammars with dynamic node relabeling ⋮ Separating \(k\)-separated eNCE graph languages ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ A characterisation of clique-width through nested partitions ⋮ The evaluation of first-order substitution is monadic second-order compatible ⋮ Hypergraph languages of bounded degree

Cites Work

This page was built for publication: Handle-rewriting hypergraph grammars