Multiset controlled grammars

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


This study focusses on defining a new variant of regulated grammars called multiset controlled grammars as well as investigating their computational power. In general, a multiset controlled grammar is a grammar equipped with an arithmetic expression over multisets terminals where to every production in the grammar a multiset is assigned, which represents the number of the occurrences of terminals on the right-hand side of the production. Then a derivation in the grammar is said to be successful if only if its multiset value satisfies a certain relational condition. In the study, we have found that control by multisets is powerful tool and yet a simple method in regulation of generative processes in grammars. We have shown that multiset controlled grammars are at least as powerful as additive valence grammars, and they are at most powerful as matrix grammars.

Original languageEnglish
Pages (from-to)6089-6098
Number of pages10
JournalJournal of Theoretical and Applied Information Technology
Issue number22
Publication statusPublished - Nov 30 2017
Externally publishedYes


  • Context-free Grammars
  • Generative Capacity
  • Multisets
  • Regulated Grammars

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Multiset controlled grammars'. Together they form a unique fingerprint.

Cite this