Petri net controlled grammars with a bounded number of additional places

Jürgen Dassow, Sherzod Turaev

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


A context-free grammar and its derivations can be described by a Petri net, called a context-free Petri net, whose places and transitions correspond to the nonterminals and the production rules of the grammar, respectively, and tokens are separate instances of the nonterminals in a sentential form. Therefore, the control of the derivations in a context-free grammar can be implemented by adding some features to the associated cf Petri net. The addition of new places and new arcs from/to these new places to/from transitions of the net leads grammars controlled by k-Petri nets, i.e., Petri nets with additional k places. In the paper we investigate the generative power and give closure properties of the families of languages generated by such Petri net controlled grammars, in particular, we show that these families form an infinite hierarchy with respect to the numbers of additional places.

Original languageEnglish
Pages (from-to)609-634
Number of pages26
JournalActa Cybernetica
Issue number3
Publication statusPublished - 2010
Externally publishedYes


  • Grammars
  • Grammars with regulated rewriting
  • Petri net controlled grammars
  • Petri nets

ASJC Scopus subject areas

  • Software
  • Computer Science (miscellaneous)
  • Computer Vision and Pattern Recognition
  • Management Science and Operations Research
  • Information Systems and Management
  • Electrical and Electronic Engineering


Dive into the research topics of 'Petri net controlled grammars with a bounded number of additional places'. Together they form a unique fingerprint.

Cite this