Multiset Controlled Grammars: A Simple Method in Regulated Rewriting Theory

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

doi:10.11591/ijeecs.v8.i1.pp36-42

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 journal › Article › peer-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 language	English
Pages (from-to)	36-42
Number of pages	7
Journal	Indonesian Journal of Electrical Engineering and Computer Science
Volume	8
Issue number	1
DOIs	https://doi.org/10.11591/ijeecs.v8.i1.pp36-42
Publication status	Published - Oct 2017
Externally published	Yes

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

Access to Document

10.11591/ijeecs.v8.i1.pp36-42

Cite this

@article{faed1a9dcae0446aaf44e113d9fe7ce8,

title = "Multiset Controlled Grammars: A Simple Method in Regulated Rewriting Theory",

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.",

keywords = "Closure property, Generative capacity, Multiset, Multiset controlled grammar, Regulated grammar",

author = "Salbiah Ashaari and Sherzod Turaev and Tamrin, {M. Izzuddin M.} and Abdurahim Okhunov and Tamara Zhukabayeva",

year = "2017",

month = oct,

doi = "10.11591/ijeecs.v8.i1.pp36-42",

language = "English",

volume = "8",

pages = "36--42",

journal = "Indonesian Journal of Electrical Engineering and Computer Science",

issn = "2502-4752",

publisher = "Institute of Advanced Engineering and Science",

number = "1",

}

TY - JOUR

T1 - Multiset Controlled Grammars

T2 - A Simple Method in Regulated Rewriting Theory

AU - Ashaari, Salbiah

AU - Turaev, Sherzod

AU - Tamrin, M. Izzuddin M.

AU - Okhunov, Abdurahim

AU - Zhukabayeva, Tamara

PY - 2017/10

Y1 - 2017/10

N2 - 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.

AB - 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.

KW - Closure property

KW - Generative capacity

KW - Multiset

KW - Multiset controlled grammar

KW - Regulated grammar

UR - http://www.scopus.com/inward/record.url?scp=85037643408&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85037643408&partnerID=8YFLogxK

U2 - 10.11591/ijeecs.v8.i1.pp36-42

DO - 10.11591/ijeecs.v8.i1.pp36-42

M3 - Article

AN - SCOPUS:85037643408

SN - 2502-4752

VL - 8

SP - 36

EP - 42

JO - Indonesian Journal of Electrical Engineering and Computer Science

JF - Indonesian Journal of Electrical Engineering and Computer Science

IS - 1

ER -

Multiset Controlled Grammars: A Simple Method in Regulated Rewriting Theory

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this