Multiset Controlled Grammars: A Simple Method in Regulated Rewriting Theory

Salbiah Ashaari, Sherzod Turaev, M. Izzuddin M. Tamrin, Abdurahim Okhunov, Tamara Zhukabayeva

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)36-42
Number of pages7
JournalIndonesian Journal of Electrical Engineering and Computer Science
Issue number1
Publication statusPublished - Oct 2017
Externally publishedYes


  • Closure property
  • Generative capacity
  • Multiset
  • Multiset controlled grammar
  • Regulated grammar

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering


Dive into the research topics of 'Multiset Controlled Grammars: A Simple Method in Regulated Rewriting Theory'. Together they form a unique fingerprint.

Cite this