Logical description of context-free graph languages
From MaRDI portal
Publication:1384534
DOI10.1006/JCSS.1997.1510zbMATH Open0897.68061OpenAlexW4212959352MaRDI QIDQ1384534FDOQ1384534
Authors: Joost Engelfriet, Vincent van Oostrom 
Publication date: 4 August 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2f25daace8a1975161fd28ce9e20b1a203e81640
Recommendations
- Regular description of context-free graph languages
- scientific article; zbMATH DE number 177436
- scientific article; zbMATH DE number 3909759
- Graph operators and its applications to context free languages
- scientific article; zbMATH DE number 2079028
- scientific article; zbMATH DE number 177789
- scientific article; zbMATH DE number 3976320
- Verification of graph grammars using a logical approach
- scientific article; zbMATH DE number 1923045
Cites Work
- Title not available (Why is that?)
- Hyperedge replacement: grammars and languages
- Complement reducible graphs
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Monadic second-order definable graph transductions: a survey
- Title not available (Why is that?)
- Handbook of Graph Grammars and Computing by Graph Transformation
- Title not available (Why is that?)
- Weak Second‐Order Arithmetic and Finite Automata
- Title not available (Why is that?)
- Decision Problems of Finite Automata Design and Related Arithmetics
- Generalized finite automata theory with an application to a decision problem of second-order logic
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Monadic second-order evaluations on tree-decomposable graphs
- Title not available (Why is that?)
- Tree acceptors and some of their applications
- Efficient decision procedures for graph properties on context-free graph languages
- Algebraic automata and context-free sets
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Linear graph grammars: Power and complexity
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Boundary graph grammars with dynamic edge relabeling
- Title not available (Why is that?)
- Context-free graph languages of bounded degree are generated by apex graph grammars
- Title not available (Why is that?)
- A comparison of boundary graph grammars and context-free hypergraph grammars
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- Structural properties of context-free sets of graphs generated by vertex replacement
- Graph expressions and graph rewritings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Regular description of context-free graph languages
- Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
- Graph grammars and their application to computer science. 4th international workshop, Bremen, Germany, March 5-9, 1990. Proceedings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combinatorial properties of boundary NLC graph languages
- Title not available (Why is that?)
- A regular characterization of graph languages definable in monadic second-order logic
- Graph grammars and their application to computer science. 5th international workshop, Williamsburg, VA, USA, November 13--18, 1994. Selected papers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Metatheorems for decision problems on hyperedge replacement graph languages
Cited In (16)
- Weighted tree automata and weighted logics
- Recognizability, hypergraph operations, and logical types
- The Structure of Level-k Phylogenetic Networks
- Context-Sensitive Languages, Rational Graphs and Determinism
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- On the structure of linear apex NLC graph grammars
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Title not available (Why is that?)
- Practical and efficient split decomposition via graph-labelled trees
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Title not available (Why is that?)
- On spectra of sentences of monadic second order logic with counting
- Title not available (Why is that?)
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
This page was built for publication: Logical description of context-free graph languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384534)
