Power properties of NLC graph grammars with a polynomial membership problem

DOI10.1016/S0304-3975(97)00212-0zbMath0911.68106MaRDI QIDQ1129012

Mariusz Flasiński

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

membership problemgraph grammarsgraph parsing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42)

Related Items (4)

Algorithmic uses of the Feferman-Vaught theorem ⋮ Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ On the structure of linear apex NLC graph grammars

Cites Work

• 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
• Restrictions on NLC graph grammars
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Nonterminal bounded NLC graph grammars
• Parsing of edNLC-graph grammars for scene analysis
• On the structure of node-label-controlled graph languages
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Graph grammars with neighbourhood-controlled embedding
• Graph grammars and their application to computer science. 4th international workshop, Bremen, Germany, March 5-9, 1990. Proceedings
• A class of linearly parsable graph grammars
• Linear graph grammars: Power and complexity
• Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
• Use of graph grammars for the description of mechanical parts
• Plex languages
• Pair grammars, graph languages and string-to-graph translations
• Parsing and Translation of (Attributed) Expansive Graph Languages for Scene Analysis
• On sequential and parallel node-rewriting graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Graph expressions and graph rewritings
• First Order Graph Grammars
• Context-free graph grammars
• Syntax-Directed Transduction
• Properties of deterministic top-down grammars
• Separable graphs, planar graphs and web grammars

This page was built for publication: Power properties of NLC graph grammars with a polynomial membership problem