Structural properties of place-labeled Petri net controlled grammars

Mohamad Jan, Nurhidaya and Turaev, Sherzod and Fong, Wan Heng and Sarmin, Nor Haniza (2014) Structural properties of place-labeled Petri net controlled grammars. In: The 3rd International Conference on Computer Engineering and Mathematical Sciences (ICCEMS 2014), 4-5 Dec 2014, Langkawi, Kedah.

PDF - Published Version Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

A place-labeled Petri net controlled grammar 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 of 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 investigate the structural properties of place-labeled Petri net controlled grammar related to control Petri nets. We show that removing useless places and transitions does not effect the generative capacity of the pPN controlled grammars. Moreover, we prove that for each pPN controlled grammar, we can construct an equivalent place-labeled ordinary net controlled grammar. Lastly, we show that the hierarchy problem for place-labeled bounded Petri net controlled grammars can be solved effectively.

Item Type:	Conference or Workshop Item (Full Paper)
Additional Information:	6846/42431 (ISBN: 9789671141472)
Uncontrolled Keywords:	Petri nets, context-free grammars, Petri net controlled grammars, structural properties
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. Sherzod Turaev
Date Deposited:	20 Apr 2015 10:01
Last Modified:	20 Apr 2015 10:01
URI:	http://irep.iium.edu.my/id/eprint/42431

Actions (login required)

View Item