Concurrently controlled grammars

Gairatzhan Mavlankulov; Mohamed Othman; Sherzod Turaev; Mohd Hasan Selamat; Laula Zhumabayeva; Tamara Zhukabayeva

doi:10.14736/kyb-2018-4-0748

Concurrently controlled grammars

Gairatzhan Mavlankulov, Mohamed Othman, Sherzod Turaev, Mohd Hasan Selamat, Laula Zhumabayeva, Tamara Zhukabayeva

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

This paper introduces a new variant of Petri net controlled grammars, namely a concurrently controlled grammar, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational power whereas the maximal firing modes increase the power of concurrently controlled grammars with erasing rules up to Turing machines.

Original language	English
Pages (from-to)	748-764
Number of pages	17
Journal	Kybernetika
Volume	54
Issue number	4
DOIs	https://doi.org/10.14736/kyb-2018-4-0748
Publication status	Published - 2018
Externally published	Yes

Keywords

Concurrent grammars
Controlled grammars
Parallel computing
Petri net

ASJC Scopus subject areas

Software
Control and Systems Engineering
Theoretical Computer Science
Information Systems
Artificial Intelligence
Electrical and Electronic Engineering

Access to Document

10.14736/kyb-2018-4-0748

Cite this

@article{e7f339ca1c1045b5a14aebc57eac91e3,

title = "Concurrently controlled grammars",

abstract = "This paper introduces a new variant of Petri net controlled grammars, namely a concurrently controlled grammar, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational power whereas the maximal firing modes increase the power of concurrently controlled grammars with erasing rules up to Turing machines.",

keywords = "Concurrent grammars, Controlled grammars, Parallel computing, Petri net",

author = "Gairatzhan Mavlankulov and Mohamed Othman and Sherzod Turaev and Selamat, {Mohd Hasan} and Laula Zhumabayeva and Tamara Zhukabayeva",

year = "2018",

doi = "10.14736/kyb-2018-4-0748",

language = "English",

volume = "54",

pages = "748--764",

journal = "Kybernetika",

issn = "0023-5954",

publisher = "Academy of Sciences of the Czech Republic",

number = "4",

}

TY - JOUR

T1 - Concurrently controlled grammars

AU - Mavlankulov, Gairatzhan

AU - Othman, Mohamed

AU - Turaev, Sherzod

AU - Selamat, Mohd Hasan

AU - Zhumabayeva, Laula

AU - Zhukabayeva, Tamara

PY - 2018

Y1 - 2018

N2 - This paper introduces a new variant of Petri net controlled grammars, namely a concurrently controlled grammar, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational power whereas the maximal firing modes increase the power of concurrently controlled grammars with erasing rules up to Turing machines.

AB - This paper introduces a new variant of Petri net controlled grammars, namely a concurrently controlled grammar, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational power whereas the maximal firing modes increase the power of concurrently controlled grammars with erasing rules up to Turing machines.

KW - Concurrent grammars

KW - Controlled grammars

KW - Parallel computing

KW - Petri net

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

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

U2 - 10.14736/kyb-2018-4-0748

DO - 10.14736/kyb-2018-4-0748

M3 - Article

AN - SCOPUS:85056148268

SN - 0023-5954

VL - 54

SP - 748

EP - 764

JO - Kybernetika

JF - Kybernetika

IS - 4

ER -

Concurrently controlled grammars

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this