Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU82576" target="_blank" >RIV/00216305:26230/09:PU82576 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Original language description

This paper studies cooperating distributed grammar systems working in the terminal derivation mode where the components are variants of permitting grammars. It proves that although the family of permitting languages is strictly included in the family ofrandom context languages, the families of random context languages and languages generated by permitting cooperating distributed grammar systems in the above mentioned derivation mode coincide. Moreover, if the components are so-called left-permitting grammars, then cooperating distributed grammar systems in the terminal mode characterize the class of context-sensitive languages, or if erasing rules are allowed, the class of recursively enumerable languages. Descriptional complexity results are also presented. It is shown that the number of permitting components can be bounded, in the case of left-permitting components with erasing rules even together with the number of nonterminals.<br><br>

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BD - Information theory

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2009

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Romanian Journal of Information Science and Technology (ROMJIST)

ISSN

1453-8245

e-ISSN

—

Volume of the periodical

12

Issue of the periodical within the volume

2

Country of publishing house

RO - ROMANIA

Number of pages

15

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—