Reproduce “Capacity Bounded Grammars and Petri Nets” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ralf Stiebe, Sherzod Turaev
The paper introduces and formally characterizes capacity-bounded grammars, which restrict the individual occurrences of nonterminals, and examines Petri net controlled grammars with place capacities. It demonstrates that these new grammar types possess greater generative power compared to previously studied derivation-bounded grammars, establishing their precise relationships within the formal language hierarchy.
Key insights
- Restricting the occurrences of each individual nonterminal yields greater generative power than bounding the total number of nonterminals in a sentential form.
- For capacity-bounded grammars, assigning a capacity of 1 to each nonterminal is sufficient to achieve their full generative power.
- For certain Petri net control types (c- and s-Petri nets), implementing strong capacities on all places does not increase generative power beyond weak capacities on nonterminal-labeled places.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.