Petri net controlled grammars: The power of labeling and final markings

Jar̈urgen Dassow, Sherzod Turaev

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

Essentially, a Petri net controlled grammar is a context-free grammar equipped with a Petri net and a function which maps transitions of the net to rules of the grammar. The language consists of all terminal words that can be obtained by applying of a sequence of productions which is the image of an occurrence sequence of the Petri net under the function. We study the generative power of such grammars on the type of the function which can be a bijection or a coding or a weak coding and with respect to three types of admitted sets of occurrence sequences. We show that the generative power does not depend on the type of the function. Moreover, the restriction to occurrence sequences, which transform the initial marking to a marking in a given finite set of markings, leads to a more powerful class of grammars than the allowance of all occurrence sequences. Furthermore, we present some new characterizations of the family of matrix languages in terms of Petri net controlled grammars.

Original languageEnglish
Pages (from-to)191-207
Number of pages17
JournalRomanian Journal of Information Science and Technology
Volume12
Issue number2
Publication statusPublished - 2009
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Petri net controlled grammars: The power of labeling and final markings'. Together they form a unique fingerprint.

Cite this