Power properties of NLC graph grammars with a polynomial membership problem

DOI10.1016/S0304-3975(97)00212-0zbMATH Open0911.68106MaRDI QIDQ1129012FDOQ1129012

Authors: Mariusz Flasiński 

Publication date: 13 August 1998

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

Recommendations

• scientific article; zbMATH DE number 3885330
• scientific article; zbMATH DE number 3872712
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Results of NLC grammars with one-letter terminal alphabets
• scientific article

zbMATH Keywords

graph grammarsmembership problemgraph 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)

Cites Work

• Title not available (Why is that?)
• Syntax-Directed Transduction
• Properties of deterministic top-down grammars
• On the structure of node-label-controlled graph languages
• Title not available (Why is that?)
• Graph grammars with neighbourhood-controlled embedding
• Linear graph grammars: Power and complexity
• On sequential and parallel node-rewriting graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Title not available (Why is that?)
• Pair grammars, graph languages and string-to-graph translations
• Plex languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph expressions and graph rewritings
• 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
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parsing of edNLC-graph grammars for scene analysis
• Parsing and Translation of (Attributed) Expansive Graph Languages for Scene Analysis
• Restrictions on NLC graph grammars
• Nonterminal bounded NLC graph grammars
• Title not available (Why is that?)
• A class of linearly parsable graph grammars
• Title not available (Why is that?)
• Context-free graph grammars
• Use of graph grammars for the description of mechanical parts
• Title not available (Why is that?)
• First Order Graph Grammars
• Separable graphs, planar graphs and web grammars

Cited In (13)

• Title not available (Why is that?)
• Algorithmic uses of the Feferman-Vaught theorem
• Title not available (Why is that?)
• On the structure of linear apex NLC graph grammars
• Characterizing compressibility of disjoint subgraphs with NLC grammars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamental methodological issues of syntactic pattern recognition
• Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
• Parsing of edNLC-graph grammars for scene analysis
• Title not available (Why is that?)
• Inference of parsable graph grammars for syntactic pattern recognition
• A polynomial algorithm for the membership problem with categorial grammars

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1129012)