On the structure of linear apex NLC graph grammars

DOI10.1016/J.TCS.2012.02.038zbMath1247.68120OpenAlexW2032682009MaRDI QIDQ441855

Changwook Kim

Publication date: 8 August 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.038

zbMATH Keywords

complexitydecidabilityformal languagesgraph grammarsstructural restrictionsnode replacement system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Power properties of NLC graph grammars with a polynomial membership problem
• On the structure of node-label-controlled graph languages
• Graph grammars with neighbourhood-controlled embedding
• Separating \(k\)-separated eNCE graph languages
• Monadic second-order definable graph transductions: a survey
• Logical description of context-free graph languages
• A hierarchy of eNCE families of graph languages
• Linear graph grammars: Power and complexity
• Node replacement graph languages squeezed with chains, trees, and forests
• Neighborhood-uniform NLC grammars
• On sequential and parallel node-rewriting graph grammars
• Complexity of boundary graph languages
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Nondeterministic Space is Closed under Complementation
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Efficient recognition algorithms for boundary and linear eNCE graph languages
• Separation results for separated apex NLC and NCE graph languages

This page was built for publication: On the structure of linear apex NLC graph grammars