Multiset controlled grammars: A normal form and closure properties

Ashaari, Salbiah and Turaev, Sherzod and Mohd Tamrin, Mohd Izzuddin and Okhunov, Abdurahim and Zhukabayeva, Tamara (2017) Multiset controlled grammars: A normal form and closure properties. Indonesian Journal of Electrical Engineering and Computer Science, 8 (1). pp. 36-42. ISSN 2502-4760

	PDF - Published Version Restricted to Registered users only Download (155kB) | Request a copy
Preview	PDF (SCOPUS) Download (219kB) | Preview

Abstract

Multisets are very powerful and yet simple control mechanisms in regulated rewriting systems. In this paper, we review back the main results on the generative power of multiset controlled grammars introduced in recent research. It was proven that multiset controlled grammars are at least as powerful as additive valence grammars and at most as powerful as matrix grammars. In this paper, we mainly investigate the closure properties of multiset controlled grammars. We show that the family of languages generated by multiset controlled grammars is closed under operations union, concatenation, kleene-star, homomorphism and mirror image.

Item Type:	Article (Journal)
Additional Information:	6846/59820
Uncontrolled Keywords:	multiset, regulated grammar, multiset controlled grammar, generative capacity, closure property
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 Engineering Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Dr. Sherzod Turaev
Date Deposited:	07 Dec 2017 10:38
Last Modified:	17 Jan 2018 11:30
URI:	http://irep.iium.edu.my/id/eprint/59820

Actions (login required)

View Item