REVIEW 1 major objections 2 minor 10 references
Structured cospan grammars generate the same languages as their discrete counterparts for graphs, hypergraphs, Petri nets and typed variants.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.3
2026-05-24 15:26 UTC
load-bearing objection The paper builds a 2-categorical framework for structured cospan grammars and proves language equivalence to discrete grammars for graphs, hypergraphs, and Petri nets once adhesivity or topos conditions are met. the 1 major comments →
Rewriting Structured Cospans
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Structured cospans model open networks with explicit interfaces. When the category they form is adhesive or a topos, double pushout rewriting is available. Structured cospan grammars are assembled via a 2-categorical construction that tracks composition and rewrites simultaneously. For graphs, hypergraphs, Petri nets and their typed variants, every such grammar yields exactly the same language as the discrete grammar obtained by forgetting the structure on the interfaces. This identity furnishes an inductive characterization of the languages and thereby generalizes classical results in graph transformation.
What carries the argument
The category whose objects are structured cospans, which supports double pushout rewriting when adhesive or a topos, together with the 2-categorical construction that assigns languages to structured cospan grammars.
Load-bearing premise
The category of structured cospans must be adhesive or a topos so that double pushout rewriting is defined.
What would settle it
A concrete grammar on graphs (or hypergraphs or Petri nets) whose generated language under structured cospan rewriting differs from the language under the corresponding discrete grammar.
If this is right
- Double pushout rewriting applies directly to open networks modeled by structured cospans.
- Languages of structured cospan grammars admit an inductive characterization via the discrete case.
- Classical results on graph rewriting extend to hypergraphs, Petri nets and their typed versions.
- Composition of networks and their rewrite dynamics are handled uniformly in one 2-categorical framework.
Where Pith is reading between the lines
- The equivalence may simplify computation of reachable configurations in open network models by reducing to the discrete setting.
- Similar language-equivalence results could be sought for other categorical presentations of systems with interfaces.
- The 2-categorical language construction might extend to higher-order rewriting or to models with additional structure such as metrics or probabilities.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops a rewriting theory for structured cospans to extend compositional modeling of open networks. It introduces a category whose objects are structured cospans and establishes conditions under which this category is adhesive or a topos, thereby guaranteeing that double-pushout rewriting applies. Structured cospan grammars are defined, with languages constructed via 2-categorical composition of rewrites. The central result is that, for graphs, hypergraphs, Petri nets, and their typed variants, any grammar induces the same language as its corresponding discrete grammar, yielding an inductive characterization of rewriting that generalizes classical graph transformation.
Significance. If the stated adhesivity and topos conditions hold, the work provides a uniform framework for rewriting in open network models that includes Petri nets. The equivalence between general and discrete grammars is a substantive generalization of prior results and enables inductive reasoning. The manuscript explicitly constructs the required conditions for DPO rewriting and applies them to the listed examples; the stress-test concern that adhesivity may fail for Petri nets therefore does not land on the paper as written.
major comments (1)
- [§4] §4 (conditions for adhesivity/topos structure): the paper states general conditions but does not include an explicit verification that the concrete category of (typed) Petri nets satisfies all required pushouts and van Kampen squares; this verification is load-bearing for the claim that DPO rewriting is available and hence for the language-equivalence theorem in the Petri-net case.
minor comments (2)
- The 2-categorical construction of languages (around the definition of grammar-induced languages) would benefit from a short diagram illustrating the horizontal and vertical composition steps.
- Notation for structured cospans is introduced without a consolidated table of symbols; adding one would improve readability for readers outside category theory.
Simulated Author's Rebuttal
We thank the referee for their careful reading, positive assessment of the significance of the work, and constructive feedback. We address the single major comment below.
read point-by-point responses
-
Referee: [§4] §4 (conditions for adhesivity/topos structure): the paper states general conditions but does not include an explicit verification that the concrete category of (typed) Petri nets satisfies all required pushouts and van Kampen squares; this verification is load-bearing for the claim that DPO rewriting is available and hence for the language-equivalence theorem in the Petri-net case.
Authors: We agree that an explicit verification for the category of (typed) Petri nets is not provided in the current manuscript, even though the general conditions are stated in §4 and the Petri-net case is included among the claimed applications. This verification is indeed load-bearing for the DPO rewriting claim and the subsequent language-equivalence theorem in that setting. In the revised manuscript we will add a detailed check (as a new subsection or short appendix) confirming that the required pushouts and van Kampen squares exist in the concrete category of (typed) Petri nets, thereby making the application fully rigorous. revision: yes
Circularity Check
No circularity: sequential categorical development with independent constructions
full rationale
The paper first proves adhesivity or topos structure for the structured cospan category under explicit conditions, then uses that to enable DPO rewriting, defines grammars and languages via 2-categorical composition of rewrites, and derives the language-equivalence result for graphs, hypergraphs, Petri nets and typed variants as a direct consequence. None of these steps reduce by definition or construction to fitted parameters, self-referential renaming, or load-bearing self-citations; the equivalence theorem follows from the prior independent categorical results rather than presupposing its own conclusion. The derivation is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The category of structured cospans is adhesive or a topos under stated conditions
Cite this review
Pith. "Pith review of Rewriting Structured Cospans." pith.science (2026). https://pith.science/paper/2001.09029
@misc{pith2026200109029,
author = {Pith},
title = {Pith review of: Rewriting Structured Cospans},
year = {2026},
howpublished = {\url{https://pith.science/paper/2001.09029}},
note = {Machine review of arXiv:2001.09029}
}
read the original abstract
We develop a theory of rewriting for structured cospans in order to extend compositional methods for modeling open networks. First, we introduce a category whose objects are structured cospans, and establish conditions under which it is adhesive or a topos. These results guarantee that double pushout rewriting can be applied in this setting. We then define structured cospan grammars and construct their associated languages via a 2-categorical framework, capturing both network composition and rewrite dynamics. As an application, we show that for graphs, hypergraphs, Petri nets, and their typed variants, any grammar induces the same language as its corresponding discrete grammar. This equivalence enables an inductive characterization of rewriting, thereby generalizing classical results from graph transformation to a broader class of categorical models.
Reference graph
Works this paper leans on
-
[1]
John Baez and Kenny Courser. Structured cospans. arXiv preprint axXiv:1911.04630 . (Re- ferred to on page 3, 11.)
-
[2]
On certain formal properties of grammars
Noam Chomsky. On certain formal properties of grammars. Information and control , 2(2):137–167, 1959. (Referred to on page 22.)
work page 1959
-
[3]
Daniel Cicala. Categorifying the zx-calculus. In Bob Co ecke and Aleks Kissinger, editors, Proceedings 14th International Conference on Quantum Physics and Logic, Nijmegen, The Netherlands, 3-7 July 2017, volume 266 of Electronic Proceedings in Theoretical Computer Science, pages 294–314. Open Publishing Association, 2018. (Refer red to on page 4, 22.)
work page 2017
-
[4]
Daniel Cicala and Kenny Courser. Spans of cospans in a top os. Theory Appl. Categ. , 33:Paper No. 1, 1–22, 2018. (Referred to on page 19.)
work page 2018
-
[5]
Grap h-grammars: an algebraic ap- proach
Harmut Ehrig, Michael Pfender, and Hans Schneider. Grap h-grammars: an algebraic ap- proach. In 14th Annual IEEE Symposium on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973) , pages 167–180. 1973. (Referred to on page 8, 21, 22.)
work page 1973
-
[6]
An inductive view of gra ph transformation
Fabio Gadducci and Reiko Heckel. An inductive view of gra ph transformation. In Recent trends in algebraic development techniques (Tarquinia, 19 97), volume 1376 of Lecture Notes in Comput. Sci. , pages 223–237. Springer, Berlin, 1998. (Referred to on pag e 6.) REWRITING STRUCTURED COSPANS 29
work page 1998
-
[7]
Sketches of an elephant: A topos theory compendium , volume 2
Peter Johnstone. Sketches of an elephant: A topos theory compendium , volume 2. Oxford University Press, 2002. (Referred to on page 21.)
work page 2002
-
[8]
Stephen Lack and Pawel Soboci´ nski. Adhesive categorie s. In Foundations of software science and computation structures , volume 2987 of Lecture Notes in Comput. Sci. , pages 273–288. Springer, Berlin, 2004. (Referred to on page 3, 8, 9.)
work page 2004
-
[9]
Stephen Lack and Pawel Soboci´ nski. Toposes are adhesive. In Graph transformations, volume 4178 of Lecture Notes in Comput. Sci. , pages 184–198. Springer, Berlin, 2006. (Referred to on page 3, 8.)
work page 2006
-
[10]
Gavin W raith. Artin glueing. J. Pure Appl. Algebra , 4:345–348, 1974. (Referred to on page 13.) E-mail address : dcicala@newhaven.edu Department of Mathematics and Physics, University of New Haven
work page 1974
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.