A new variant of Petri net controlled grammars

Nurhidaya Mohamad Jan, Sherzod Turaev, Wan Heng Fong, Nor Haniza Sarmin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A Petri net controlled grammar is a Petri net with respect to a context-free grammar where the successful derivations of the grammar can be simulated using the occurrence sequences of the net. In this paper, we introduce a new variant of Petri net controlled grammars, called a place-labeled Petri net controlled grammar, which is a context-free grammar equipped with a Petri net and a function which maps places of the net to productions of the grammar. The language consists of all terminal strings that can be obtained by parallelly applying multisets of the rules which are the images of the sets of the input places of transitions in a successful occurrence sequence of the Petri net. We study the effect of the different labeling strategies to the computational power and establish lower and upper bounds for the generative capacity of place-labeled Petri net controlled grammars.

Original languageEnglish
Title of host publication22nd National Symposium on Mathematical Sciences, SKSM 2014
Subtitle of host publicationStrengthening Research and Collaboration of Mathematical Sciences in Malaysia
EditorsIbrahim Mohamed, Wong Kok Bin, Angelina Chin Yan Mui, Loo Tee How
PublisherAmerican Institute of Physics Inc.
ISBN (Electronic)9780735413290
DOIs
Publication statusPublished - Oct 22 2015
Externally publishedYes
Event22nd National Symposium on Mathematical Sciences: Strengthening Research and Collaboration of Mathematical Sciences in Malaysia, SKSM 2014 - Selangor, Malaysia
Duration: Nov 24 2014Nov 26 2014

Publication series

NameAIP Conference Proceedings
Volume1682
ISSN (Print)0094-243X
ISSN (Electronic)1551-7616

Conference

Conference22nd National Symposium on Mathematical Sciences: Strengthening Research and Collaboration of Mathematical Sciences in Malaysia, SKSM 2014
Country/TerritoryMalaysia
CitySelangor
Period11/24/1411/26/14

Keywords

  • Computational Power
  • Context-Free Grammar
  • Petri Net
  • Petri Net Controlled Grammar

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Fingerprint

Dive into the research topics of 'A new variant of Petri net controlled grammars'. Together they form a unique fingerprint.

Cite this