Place-labelled petri net controlled grammars

Mohamad Jan, Nurhidaya and Turaev, Sherzod and Fong, Wan Heng and Sarmin, Nor Haniza (2017) Place-labelled petri net controlled grammars. ScienceAsia, 43S. pp. 9-19. ISSN 1513-1874

	PDF - Published Version Restricted to Registered users only Download (285kB) | Request a copy
Preview	PDF (SCOPUS) - Supplemental Material Download (66kB) | Preview
Preview	PDF (WOS) - Supplemental Material Download (134kB) | Preview

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.

Item Type:	Article (Journal)
Additional Information:	6846/58699
Uncontrolled Keywords:	context-free grammars, computational power, 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:	09 Oct 2017 12:20
Last Modified:	09 Oct 2017 12:20
URI:	http://irep.iium.edu.my/id/eprint/58699

Actions (login required)

View Item