scientific article; zbMATH DE number 1142315
From MaRDI portal
Publication:4385531
zbMath0900.68282MaRDI QIDQ4385531
Publication date: 14 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Related Items (only showing first 100 items - show all)
A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Polypodic codes ⋮ Recognizable sets of graphs: equivalent definitions and closure properties ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Property Testing for Bounded Degree Databases ⋮ Rewriting logic as a semantic framework for concurrency: a progress report ⋮ Faster Property Testers in a Variation of the Bounded Degree Model ⋮ A uniform approach to graph rewriting: The pullback approach ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ A declarative approach to graph based modeling ⋮ On reduction algorithms for graphs with small treewidth ⋮ Reduction algorithms for constructing solutions in graphs with small treewidth ⋮ From Tree-Based Generators to Delegation Networks ⋮ Unnamed Item ⋮ Resolution-Like Theorem Proving for High-Level Conditions ⋮ Strategic port graph rewriting: an interactive modelling framework ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ An Algorithm for Approximating the Satisfiability Problem of High-level Conditions ⋮ On the interleaving semantics of transformation units — A step into GRACE ⋮ Graph automata for linear graph languages ⋮ Concatenation of graphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ Monadic Second-Order Logic and Transitive Closure Logics over Trees ⋮ A Practical Approach to Courcelle's Theorem ⋮ Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data ⋮ Well-structured transition systems everywhere! ⋮ Monadic Second Order Logic on Graphs with Local Cardinality Constraints ⋮ The HOMFLY-PT polynomial is fixed-parameter tractable ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Proper Interval Vertex Deletion ⋮ Default logic and bounded treewidth ⋮ Constraint-preserving architecture transformations: A graph rewriting approach ⋮ On low rank-width colorings ⋮ Node rewriting in graphs and hypergraphs: A categorical framework ⋮ Constructing minimum changeover cost arborescenses in bounded treewidth graphs ⋮ Undirected Graphs of Entanglement 2 ⋮ Unnamed Item ⋮ On Making a Distinguished Vertex Minimum Degree by Vertex Deletion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Encoding Treewidth into SAT ⋮ Context-free event domains are recognizable ⋮ On the Parameterised Intractability of Monadic Second-Order Logic ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ Digraphs of Bounded Width ⋮ Model checking the full modal mu-calculus for infinite sequential processes ⋮ Monadic second-order definable graph transductions: a survey ⋮ Structural tractability of counting of solutions to conjunctive queries ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Handle-rewriting hypergraph grammars ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ The translation power of top-down tree-to-graph transducers ⋮ The complexity of first-order and monadic second-order logic revisited ⋮ Computing crossing numbers in quadratic time ⋮ An asymptotic analysis of labeled and unlabeled \(k\)-trees ⋮ Complexity of metric dimension on planar graphs ⋮ A logical approach to multicut problems ⋮ Backdoors to Satisfaction ⋮ Probabilistic hyperedge replacement grammars ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Quickly deciding minor-closed parameters in general graphs ⋮ Courcelle's theorem for triangulations ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Parameterized analysis and crossing minimization problems ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Logical description of context-free graph languages ⋮ On the rational subsets of the free group ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Equivariant unification ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Drags: a compositional algebraic framework for graph rewriting ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ The complexity of two graph orientation problems ⋮ On the transition graphs of Turing machines. ⋮ Model-checking hierarchical structures ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Linkless and flat embeddings in 3-space ⋮ Obtaining a planar graph by vertex deletion ⋮ Fixpoint logics over hierarchical structures ⋮ Tractable cases of the extended global cardinality constraint ⋮ Proper interval vertex deletion ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Graph transformation for incremental natural language analysis ⋮ Model checking the full modal mu-calculus for infinite sequential processes ⋮ Reversibility of computations in graph-walking automata ⋮ On the complexity of core, kernel, and bargaining set ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Faster parameterized algorithms for minor containment ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
This page was built for publication:
