On the public citation graph

The complexity of graph languages generated by hyperedge replacement

https://doi.org/10.1007/bf00289017
0 signed · 89 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-18771-5_48openalex-snapshot
On partially ordered graph grammars
inferredcites →https://doi.org/10.1007/3-540-18771-5_62openalex-snapshot
Practical applications of precedence graph grammars
inferredcites →https://doi.org/10.1007/3-540-19488-6_128openalex-snapshot
Efficient algorithms on context-free graph languages
inferredcites →https://doi.org/10.1007/3-540-50939-9_138openalex-snapshot
Decidable boundedness problems for hyperedge-replacement graph grammars
inferredcites →https://doi.org/10.1007/bf00288976openalex-snapshot
Metatheorems for decision problems on hyperedge replacement graph languages
inferredcites →https://doi.org/10.1007/bf00289155openalex-snapshot
A class of linearly parsable graph grammars
inferredcites →https://doi.org/10.1007/bf01692060openalex-snapshot
Graph expressions and graph rewritings
inferredcites →https://doi.org/10.1007/bfb0000094openalex-snapshot
Graph-Grammars and Their Application to Computer Science
inferredcites →https://doi.org/10.1007/bfb0025713openalex-snapshot
Graph-Grammars and Their Application to Computer Science and Biology
inferredcites →https://doi.org/10.1007/bfb0026094openalex-snapshot
Decomposition trees: Structured graph representation and efficient algorithms
inferredcites →https://doi.org/10.1007/bfb0039608openalex-snapshot
Some structural aspects of hypergraph languages generated by hyperedge replacement
inferredcites →https://doi.org/10.1016/0020-0190(82)90086-2openalex-snapshot
Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
inferredcites →https://doi.org/10.1016/0022-0000(80)90036-7openalex-snapshot
Tree-size bounded alternation
inferredcites →https://doi.org/10.1016/0096-0551(80)90011-9openalex-snapshot
Introduction to automata theory, languages, and computation
inferredcites →https://doi.org/10.1016/0166-218x(87)90051-5openalex-snapshot
String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
inferredcites →https://doi.org/10.1016/0196-6774(86)90023-4openalex-snapshot
Graph minors. II. Algorithmic aspects of tree-width
inferredcites →https://doi.org/10.1016/0304-3975(87)90102-2openalex-snapshot
An axiomatic definition of context-free rewriting and its application to NLC graph grammars
inferredcites →https://doi.org/10.1016/0378-4754(81)90068-9openalex-snapshot
Introduction to automata theory, languages and computation
inferredcites →https://doi.org/10.1016/0890-5401(89)90030-8openalex-snapshot
Linear graph grammars: Power and complexity
inferredcites →https://doi.org/10.1016/0890-5401(90)90038-jopenalex-snapshot
A comparison of boundary graph grammars and context-free hypergraph grammars
inferredcites →https://doi.org/10.1016/s0019-9958(78)90528-4openalex-snapshot
Context-free graph grammars
inferredcites →https://doi.org/10.1016/s0019-9958(86)80045-6openalex-snapshot
Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
inferredcites →https://doi.org/10.1016/s0020-0255(71)80008-7openalex-snapshot
Plex languages
inferredcites →https://doi.org/10.1051/ita/1990240302671openalex-snapshot
Complexity of boundary graph languages
inferredcites →https://doi.org/10.1137/0213040openalex-snapshot
On Some Variants of the Bandwidth Minimization Problem
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0608024openalex-snapshot
Complexity of Finding Embeddings in a k -Tree
inferredcites →https://doi.org/10.1145/28395.28411openalex-snapshot
Properties that characterize LOGCFL
inferredcites →https://doi.org/10.1145/321679.321682openalex-snapshot
Linear and Context-Free Graph Grammars
inferredcites →https://doi.org/10.1145/322077.322083openalex-snapshot
On the Tape Complexity of Deterministic Context-Free Languages
inferredcites →https://doi.org/10.1145/322234.322243openalex-snapshot
Alternation

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.1995.1029openalex-snapshot
Node Replacement Graph Languages Squeezed with Chains, Trees, and Forests
inferred← citeshttps://doi.org/10.1006/inco.1997.2628openalex-snapshot
The Bounded Degree Problem for eNCE Graph Grammars
inferred← citeshttps://doi.org/10.1006/jcss.2002.1851openalex-snapshot
Node Replacements in Embedding Normal Form
inferred← citeshttps://doi.org/10.1007/3-540-56402-0_51openalex-snapshot
Probabilistic graph grammars
inferred← citeshttps://doi.org/10.1007/3-540-57163-9_5openalex-snapshot
Five facets of hyperedge replacement beyond context-freeness
inferred← citeshttps://doi.org/10.1007/3-540-61228-9_100openalex-snapshot
HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting
inferred← citeshttps://doi.org/10.1007/978-3-030-13435-8_17openalex-snapshot
Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars
inferred← citeshttps://doi.org/10.1007/978-3-030-23611-3_4openalex-snapshot
Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1007/978-3-030-78946-6_9openalex-snapshot
Rule-Based Top-Down Parsing for Acyclic Contextual Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1007/978-3-032-29730-3_1openalex-snapshot
LR-Based Parsing of Hypergraph Languages: A Positional Grammar Approach
inferred← citeshttps://doi.org/10.1007/978-3-319-21145-9_2openalex-snapshot
Predictive Top-Down Parsing for Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1007/978-3-319-61470-0_7openalex-snapshot
Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1007/978-3-319-63342-8_6openalex-snapshot
Distributional Learning of Regular Formal Graph System of Bounded Degree
inferred← citeshttps://doi.org/10.1007/978-3-319-74730-9_5openalex-snapshot
Graph Rewriting Based Search for Molecular Structures: Definitions, Algorithms, Hardness
inferred← citeshttps://doi.org/10.1007/978-3-319-77313-1_24openalex-snapshot
Efficient Translation with Linear Bimorphisms
inferred← citeshttps://doi.org/10.1007/978-3-540-39917-9_19openalex-snapshot
Estimating Maximum Likelihood Parameters for Stochastic Context-Free Graph Grammars
inferred← citeshttps://doi.org/10.1007/978-3-540-46464-8_4openalex-snapshot
Neighborhood-Preserving Node Replacements
inferred← citeshttps://doi.org/10.1007/978-3-540-70590-1_18openalex-snapshot
Functional-Logic Graph Parser Combinators
inferred← citeshttps://doi.org/10.1007/978-3-540-72951-8_3openalex-snapshot
Treewidth: Structure and Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-540-87405-8_4openalex-snapshot
An Algorithm for Hypergraph Completion According to Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1007/978-3-642-24412-4_31openalex-snapshot
Distributional Learning of Simple Context-Free Tree Grammars
inferred← citeshttps://doi.org/10.1007/978-3-642-59126-6_3openalex-snapshot
Context-Free Graph Grammars
inferred← citeshttps://doi.org/10.1007/bfb0017373openalex-snapshot
A note on hyperedge replacement
inferred← citeshttps://doi.org/10.1007/bfb0017410openalex-snapshot
Tree automata, tree decomposition and hyperedge replacement
inferred← citeshttps://doi.org/10.1007/bfb0017411openalex-snapshot
Recognizing rooted context-free flowgraph languages in polynomial time
inferred← citeshttps://doi.org/10.1007/bfb0017422openalex-snapshot
Computing by graph transformation: Overall aims and new results
inferred← citeshttps://doi.org/10.1007/s10849-009-9109-6openalex-snapshot
Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars
inferred← citeshttps://doi.org/10.1016/0020-0190(93)90221-topenalex-snapshot
NP-completeness of k-connected hyperedge-replacement languages of order k
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90065-2openalex-snapshot
Recognising k-connected hypergraphs in cubic time
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00272-xopenalex-snapshot
Characterization and complexity of uniformly nonprimitive labeled 2-structures
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00202-2openalex-snapshot
Probabilistic hyperedge replacement grammars
inferred← citeshttps://doi.org/10.1016/j.jcss.2020.10.002openalex-snapshot
Uniform parsing for hyperedge replacement grammars
inferred← citeshttps://doi.org/10.1016/j.jlamp.2018.12.006openalex-snapshot
Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80050-9openalex-snapshot
The translation power of top-down tree-to-graph transducers
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00226-6openalex-snapshot
Generating irregular partitionable data structures
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00258-3openalex-snapshot
HRNCE grammars — a hypergraph generating system with an eNCE way of rewriting
inferred← citeshttps://doi.org/10.1109/access.2022.3217913openalex-snapshot
Engineering Grammar-Based Type Checking for Graph Rewriting Languages
inferred← citeshttps://doi.org/10.1109/hcc.2001.995230openalex-snapshot
Shapely hierarchical graph transformation
inferred← citeshttps://doi.org/10.1109/iiai-aai.2014.51openalex-snapshot
Polynomial Time Mat Learning of C-deterministic Regular Formal Graph Systems
inferred← citeshttps://doi.org/10.1142/9789812384720_0002openalex-snapshot
HYPEREDGE REPLACEMENT GRAPH GRAMMARS
inferred← citeshttps://doi.org/10.1162/coli_a_00309openalex-snapshot
Weighted DAG Automata for Semantic Graphs
inferred← citeshttps://doi.org/10.1162/coli_a_00350openalex-snapshot
Ordered Tree Decomposition for HRG Rule Extraction
inferred← citeshttps://doi.org/10.1162/coli_a_00488openalex-snapshot
Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies
inferred← citeshttps://doi.org/10.13053/rcs-148-3-28openalex-snapshot
Grafos de análisis sintáctico con gramáticas HRGs
inferred← citeshttps://doi.org/10.14279/tuj.eceasst.10.143openalex-snapshot
Parsing of Hyperedge Replacement Grammars with Graph Parser Combinators
inferred← citeshttps://doi.org/10.18653/v1/s17-1024openalex-snapshot
Parsing Graphs with Regular Graph Grammars
inferred← citeshttps://doi.org/10.18653/v1/w16-24openalex-snapshot
Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata
inferred← citeshttps://doi.org/10.18653/v1/w16-2407openalex-snapshot
EM-Training for Weighted Aligned Hypergraph Bimorphisms
inferred← citeshttps://doi.org/10.3115/v1/p15-1143openalex-snapshot
Graph parsing with s-graph grammars
inferred← citeshttps://doi.org/10.3233/fi-2016-1393openalex-snapshot
Designing and Learning Substitutable Plane Graph Grammars
inferred← citeshttps://doi.org/10.3390/a17060268openalex-snapshot
Parsing Unranked Tree Languages, Folded Once
inferred← citeshttps://doi.org/10.4204/eptcs.309.4openalex-snapshot
Speeding up Generalized PSR Parsers by Memoization Techniques
inferred← citeshttps://doi.org/10.4204/eptcs.417.8openalex-snapshot
Finite Automata for Efficient Graph Recognition
inferred← citeshttps://doi.org/10.48550/arxiv.2103.11089openalex-snapshot
Dependency Graph-to-String Statistical Machine Translation
inferred← citeshttps://doi.org/10.48550/arxiv.2105.02033openalex-snapshot
Polynomial Graph Parsing with Non-Structural Reentrancies
inferred← citeshttps://doi.org/10.5109/3069openalex-snapshot
Polynomial Time Algorithm Solving the Refutation Tree Problem for Formal Graph Systems
inferred← citeshttps://doi.org/10.70675/03c138dezf306z4f6cz913ez53d66dced624openalex-snapshot
Exact parameterized algorithmics for structural RNAbioinformatics
inferred← citeshttps://doi.org/10.7916/d8jh3zrropenalex-snapshot
Grammar-Based Semantic Parsing Into Graph Representations
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.