On the public citation graph

A logical characterization of the sets of hypergraphs defined by Hyperedge Replacement grammars

https://doi.org/10.1007/bf01204169
0 signed · 79 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.1002/malq.19600060105openalex-snapshot
Weak Second‐Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1006/inco.1995.1020openalex-snapshot
Structural Properties of Context-Free Sets of Graphs Generated by Vertex Replacement
inferredcites →https://doi.org/10.1006/jctb.1995.1006openalex-snapshot
Graph Minors .XIII. The Disjoint Paths Problem
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/3-540-53904-2_106openalex-snapshot
The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
inferredcites →https://doi.org/10.1007/978-3-663-09367-1openalex-snapshot
Transductions and Context-Free Languages
inferredcites →https://doi.org/10.1007/bf01691346openalex-snapshot
Generalized finite automata theory with an application to a decision problem of second-order logic
inferredcites →https://doi.org/10.1007/bf01692060openalex-snapshot
Graph expressions and graph rewritings
inferredcites →https://doi.org/10.1007/bfb0017374openalex-snapshot
Graph grammars based on node rewriting: an introduction to NLC graph grammars
inferredcites →https://doi.org/10.1007/bfb0017397openalex-snapshot
A characterization of context-free NCE graph languages by monadic second-order logic on trees
inferredcites →https://doi.org/10.1007/bfb0039608openalex-snapshot
Some structural aspects of hypergraph languages generated by hyperedge replacement
inferredcites →https://doi.org/10.1016/0022-0000(91)90018-zopenalex-snapshot
The string generating power of context-free hypergraph grammars
inferredcites →https://doi.org/10.1016/0022-0000(93)90004-gopenalex-snapshot
Handle-rewriting hypergraph grammars
inferredcites →https://doi.org/10.1016/0095-8956(86)90030-4openalex-snapshot
Graph minors. V. Excluding a planar graph
inferredcites →https://doi.org/10.1016/0166-218x(94)90019-1openalex-snapshot
The monadic second order logic of graphs VI: on several representations of graphs by relational structures
inferredcites →https://doi.org/10.1016/0304-3975(86)90050-2openalex-snapshot
Equivalences and transformations of regular systems—Applications to recursive program schemes and grammars
inferredcites →https://doi.org/10.1016/0304-3975(87)90050-8openalex-snapshot
Characteristics of graph languages generated by edge replacement
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/0304-3975(91)90387-hopenalex-snapshot
The monadic second-order logic of graphs V: on closing the gap between definability and recognizability
inferredcites →https://doi.org/10.1016/0304-3975(92)90148-9openalex-snapshot
The monadic second-order logic of graphs VII: graphs as relational structures
inferredcites →https://doi.org/10.1016/0304-3975(93)90064-zopenalex-snapshot
Monadic second-order evaluations on tree-decomposable graphs
inferredcites →https://doi.org/10.1016/0304-3975(94)90268-2openalex-snapshot
Monadic second-order definable graph transductions: a survey
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/0890-5401(90)90043-hopenalex-snapshot
The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
inferredcites →https://doi.org/10.1016/b978-0-444-88074-1.50010-xopenalex-snapshot
Graph Rewriting: An Algebraic and Logic Approach
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/s0022-0000(05)80022-4openalex-snapshot
Hypergraph languages of bounded degree
inferredcites →https://doi.org/10.1016/s0022-0000(70)80041-1openalex-snapshot
Tree acceptors and some of their applications
inferredcites →https://doi.org/10.1051/ita/1992260302571openalex-snapshot
The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

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.1999.2807openalex-snapshot
Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations
inferred← citeshttps://doi.org/10.1006/inco.2002.3130openalex-snapshot
A Monadic Second-Order Definition of the Structure of Convex Hypergraphs
inferred← citeshttps://doi.org/10.1006/jcss.1996.0087openalex-snapshot
Regular Description of Context-free Graph Languages
inferred← citeshttps://doi.org/10.1006/jcss.1997.1510openalex-snapshot
Logical Description of Context-free Graph Languages
inferred← citeshttps://doi.org/10.1006/jcss.1999.1684openalex-snapshot
A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_49openalex-snapshot
Automatic Graphs and Graph D0L-Systems
inferred← citeshttps://doi.org/10.1007/3-540-58950-3_395openalex-snapshot
Designing graph drawings by layout graph grammars
inferred← citeshttps://doi.org/10.1007/3-540-63246-8_9openalex-snapshot
Monadic second order logic and node relations on graphs and trees
inferred← citeshttps://doi.org/10.1007/978-3-540-39890-5_21openalex-snapshot
NCE Graph Grammars and Clique-Width
inferred← citeshttps://doi.org/10.1007/978-3-540-46464-8_2openalex-snapshot
Tree Languages Generated by Context-Free Graph Grammars
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_1openalex-snapshot
Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
inferred← citeshttps://doi.org/10.1007/978-3-540-79723-4_3openalex-snapshot
Algorithmic Meta-theorems
inferred← citeshttps://doi.org/10.1007/978-3-642-59126-6_3openalex-snapshot
Context-Free Graph Grammars
inferred← citeshttps://doi.org/10.1007/978-94-007-0714-6_10openalex-snapshot
Generalizing Parikh’s Theorem
inferred← citeshttps://doi.org/10.1007/bf01178511openalex-snapshot
Context-free graph languages of bounded degree are generated by apex graph grammars
inferred← citeshttps://doi.org/10.1007/bfb0036178openalex-snapshot
Generalized rational relations and their logical definability
inferred← citeshttps://doi.org/10.1007/s002240000115openalex-snapshot
A Characterization of the Sets of Hypertrees Generated by Hyperedge-Replacement Graph Grammars
inferred← citeshttps://doi.org/10.1016/0168-0072(95)94698-vopenalex-snapshot
The monadic second-order logic of graphs VIII: Orientations
inferred← citeshttps://doi.org/10.1016/j.apal.2003.11.002openalex-snapshot
Algorithmic uses of the Feferman–Vaught Theorem
inferred← citeshttps://doi.org/10.1016/j.dam.2006.06.020openalex-snapshot
Counting truth assignments of formulas of bounded tree-width or clique-width
inferred← citeshttps://doi.org/10.1016/j.jal.2005.08.004openalex-snapshot
The monadic second-order logic of graphs XV: On a conjecture by D. Seese
inferred← citeshttps://doi.org/10.1016/j.jctb.2006.04.003openalex-snapshot
Vertex-minors, monadic second-order logic, and a conjecture by Seese
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.006openalex-snapshot
Trees, grids, and MSO decidability: From graphs to matroids
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80022-4openalex-snapshot
Hypergraph languages of bounded degree
inferred← citeshttps://doi.org/10.1016/s0166-218x(00)00221-3openalex-snapshot
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00184-5openalex-snapshot
Upper bounds to the clique width of graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00168-7openalex-snapshot
Tree-based picture generation
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00449-8openalex-snapshot
Tree-width and the monadic quantifier hierarchy
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00578-9openalex-snapshot
The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00263-6openalex-snapshot
Nondeterministic operations on finite relational structures
inferred← citeshttps://doi.org/10.1017/cbo9780511974960.006openalex-snapshot
Algorithmic meta-theorems
inferred← citeshttps://doi.org/10.1017/s0960129501003565openalex-snapshot
Fusion in relational structures and the verification of monadic second-order properties
inferred← citeshttps://doi.org/10.1093/comjnl/bxae100openalex-snapshot
A comparison of reserved graph grammar and edge-based graph grammar
inferred← citeshttps://doi.org/10.1093/comjnl/bxm052openalex-snapshot
Width Parameters Beyond Tree-width and their Applications
inferred← citeshttps://doi.org/10.1109/lics.2019.8785682openalex-snapshot
Canonisation and Definability for Graphs of Bounded Rank Width
inferred← citeshttps://doi.org/10.1109/lics65433.2025.00058openalex-snapshot
Graphs of unbounded linear cliquewidth must transduce all trees
inferred← citeshttps://doi.org/10.1137/070687256openalex-snapshot
Clique-Width is NP-Complete
inferred← citeshttps://doi.org/10.1137/s0097539701394511openalex-snapshot
Macro Tree Translations of Linear Size Increase are MSO Definable
inferred← citeshttps://doi.org/10.1142/9789812384720_0002openalex-snapshot
HYPEREDGE REPLACEMENT GRAPH GRAMMARS
inferred← citeshttps://doi.org/10.1145/1132516.1132568openalex-snapshot
Clique-width minimization is NP-hard
inferred← citeshttps://doi.org/10.1145/2603088.2603118openalex-snapshot
Logical characterization of weighted pebble walking automata
inferred← citeshttps://doi.org/10.1145/3568025openalex-snapshot
Canonisation and Definability for Graphs of Bounded Rank Width
inferred← citeshttps://doi.org/10.1145/3661814.3662083openalex-snapshot
Rank-decreasing transductions
inferred← citeshttps://doi.org/10.1145/371316.371512openalex-snapshot
MSO definable string transductions and two-way finite-state transducers
inferred← citeshttps://doi.org/10.14279/tuj.eceasst.30.404openalex-snapshot
Expressiveness of graph conditions with variables
inferred← citeshttps://doi.org/10.15398/jlm.v3i1.94openalex-snapshot
A logical approach to grammar description
inferred← citeshttps://doi.org/10.2168/lmcs-10(3:2)2014openalex-snapshot
Decidability Results for the Boundedness Problem
inferred← citeshttps://doi.org/10.2168/lmcs-6(2:2)2010openalex-snapshot
On the Monadic Second-Order Transduction Hierarchy
inferred← citeshttps://doi.org/10.2178/jsl/1096901758openalex-snapshot
On spectra of sentences of monadic second order logic with counting
inferred← citeshttps://doi.org/10.48550/arxiv.2003.14177openalex-snapshot
VC density of set systems defnable in tree-like graphs
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.