| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 43 Number 4
Volume 43 Number 3
Volume 43 Number 2
Volume 43 Number 1
Volume 43S Number 1
Volume 42 Number 6
Earlier issues
Volume 43S Number 1 Volume 43 Number 1

previous article next article

Research articles

ScienceAsia 43S(2017): 9-19 |doi: 10.2306/scienceasia1513-1874.2017.43S.009

Place-labelled Petri net controlled grammars

Nurhidaya˙Mohamad˙Jana, Sherzod˙Turaevb,*, Wan˙Heng˙Fongc, Nor˙Haniza˙Sarmina

ABSTRACT:     A place-labelled Petri net (pPN) controlled grammar is a context-free grammar equipped with a Petri net and a function which maps places of the net to the productions of the grammar. The language consists of all terminal strings that can be obtained by simultaneously applying the rules of multisets which are the images of the sets of the input places of transitions in a successful occurrence sequence of the Petri net. In this paper, we study the generative power and structural properties of pPN-controlled grammars. We show that pPN-controlled grammars have the same generative power as matrix grammars. Moreover, we prove that for each pPN-controlled grammar, we can construct an equivalent place-labelled ordinary net controlled grammar.

Download PDF

10 Download 127 View

a Department˙of˙Mathematical˙Sciences, Faculty˙of˙Science, Universiti˙Teknologi˙Malaysia, 81310˙UTM˙Johor˙Bahru, Johor, Malaysia
b Department˙of˙Computer˙Science, Kulliyyah˙of˙Information˙and˙Communication˙Technology, International˙Islamic˙University˙Malaysia, 53100˙Kuala˙Lumpur, Malaysia
c Ibnu˙Sina˙Institute˙for˙Fundamental˙Science˙Studies, Universiti˙Teknologi˙Malaysia, 81310˙UTM˙Johor˙Bahru, Johor, Malaysia

* Corresponding author, E-mail: sherzod@iium.edu.my

Received 22 Aug 2014, Accepted 21 May 2017