Capacity Bounded Grammars and Petri Nets

Ralf Stiebe
Sherzod Turaev

A capacity bounded grammar is a grammar whose derivations are restricted by assigning a bound to the number of every nonterminal symbol in the sentential forms. In the paper the generative power and closure properties of capacity bounded grammars and their Petri net controlled counterparts are investigated.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 193–203.
Published: 30th July 2009.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: