On the public citation graph

A characterization of context-free NCE graph languages by monadic second-order logic on trees

https://doi.org/10.1007/bfb0017397
0 signed · 61 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.1007/3-540-18771-5_41openalex-snapshot
May we introduce to you: Hyperedge replacement
inferredcites →https://doi.org/10.1007/3-540-18771-5_44openalex-snapshot
An introduction to the NLC way of rewriting graphs
inferredcites →https://doi.org/10.1007/3-540-18771-5_52openalex-snapshot
Apex graph grammars
inferredcites →https://doi.org/10.1007/3-540-19488-6_105openalex-snapshot
Problems easy for tree-decomposable graphs extended abstract
inferredcites →https://doi.org/10.1007/3-540-19488-6_129openalex-snapshot
Efficient analysis of graph properties 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/3-540-51498-8_15openalex-snapshot
Context-free NCE graph grammars
inferredcites →https://doi.org/10.1007/978-1-4613-8928-6_22openalex-snapshot
Weak Second-Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1007/978-3-663-01443-0openalex-snapshot
Graph-Grammatiken
inferredcites →https://doi.org/10.1007/bf00288976openalex-snapshot
Metatheorems for decision problems on hyperedge replacement graph 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/bfb0017393openalex-snapshot
Graphs as relational structures : An algebraic and logical approach
inferredcites →https://doi.org/10.1007/bfb0017394openalex-snapshot
Context-free handle-rewriting hypergraph grammars
inferredcites →https://doi.org/10.1007/bfb0035847openalex-snapshot
On polynomial time graph grammars
inferredcites →https://doi.org/10.1016/0022-0000(90)90002-3openalex-snapshot
Boundary graph grammars with dynamic edge relabeling
inferredcites →https://doi.org/10.1016/0166-218x(81)90013-5openalex-snapshot
Complement reducible graphs
inferredcites →https://doi.org/10.1016/0166-218x(87)90054-0openalex-snapshot
Combinatorial properties of boundary NLC graph languages
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)90078-gopenalex-snapshot
A regular characterization of graph languages definable in monadic second-order logic
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/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/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/s0019-9958(86)80045-6openalex-snapshot
Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
inferredcites →https://doi.org/10.1016/s0022-0000(70)80041-1openalex-snapshot
Tree acceptors and some of their applications
inferredcites →https://doi.org/10.1090/s0002-9947-1961-0139530-9openalex-snapshot
Decision problems of finite automata design and related arithmetics

What points at this work

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

inferred← citeshttps://doi.org/10.1006/jcss.1996.0087openalex-snapshot
Regular 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-55251-0_7openalex-snapshot
Monadic second-order definable graph transductions
inferred← citeshttps://doi.org/10.1007/3-540-57163-9_14openalex-snapshot
Context-free graph grammars: Separating vertex replacement from hyperedge replacement
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_88openalex-snapshot
MSO definable text languages
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-030-79416-3_24openalex-snapshot
Shelah-Stupp’s and Muchnik’s Iterations Revisited
inferred← citeshttps://doi.org/10.1007/978-3-642-59126-6_3openalex-snapshot
Context-Free Graph Grammars
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/bf01204169openalex-snapshot
A logical characterization of the sets of hypergraphs defined by Hyperedge Replacement grammars
inferred← citeshttps://doi.org/10.1007/bf02679464openalex-snapshot
Monadic Second-Order Definable Text Languages
inferred← citeshttps://doi.org/10.1007/bfb0017374openalex-snapshot
Graph grammars based on node rewriting: an introduction to NLC graph grammars
inferred← citeshttps://doi.org/10.1007/bfb0017393openalex-snapshot
Graphs as relational structures : An algebraic and logical approach
inferred← citeshttps://doi.org/10.1007/bfb0017394openalex-snapshot
Context-free handle-rewriting hypergraph grammars
inferred← citeshttps://doi.org/10.1007/bfb0017422openalex-snapshot
Computing by graph transformation: Overall aims and new results
inferred← citeshttps://doi.org/10.1007/bfb0017471openalex-snapshot
Graph grammars and tree transducers
inferred← citeshttps://doi.org/10.1007/bfb0017482openalex-snapshot
Graphs and decidable transductions based on edge constraints
inferred← citeshttps://doi.org/10.1007/s00224-003-1072-zopenalex-snapshot
Tree Series Transformations that Respect Copying
inferred← citeshttps://doi.org/10.1016/0022-0000(93)90004-gopenalex-snapshot
Handle-rewriting hypergraph grammars
inferred← citeshttps://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
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/0304-3975(92)90148-9openalex-snapshot
The monadic second-order logic of graphs VII: graphs as relational structures
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(94)90268-2openalex-snapshot
Monadic second-order definable graph transductions: a survey
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.08.025openalex-snapshot
Weighted tree automata and weighted logics
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(98)00226-6openalex-snapshot
Generating irregular partitionable data structures
inferred← citeshttps://doi.org/10.1109/lics.1993.287589openalex-snapshot
Monadic second-order logic and hypergraph orientation
inferred← citeshttps://doi.org/10.1109/lics65433.2025.00058openalex-snapshot
Graphs of unbounded linear cliquewidth must transduce all trees
inferred← citeshttps://doi.org/10.1142/9789812384720_0002openalex-snapshot
HYPEREDGE REPLACEMENT GRAPH GRAMMARS
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.2139/ssrn.4571162openalex-snapshot
A New Graph Grammar Formalism for Robust Syntactic Pattern Recognition
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.