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

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.

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

Keywords

  • 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

Fingerprint

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

Cite this