Detail publikace

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

CSUHAJ-VARJÚ, E. MASOPUST, T. VASZIL, G.

Originální název

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

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 of random 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.

Klíčová slova

Cooperating distributed grammar systems, permitting grammars, left-permitting grammars, generative power.

Autoři

CSUHAJ-VARJÚ, E.; MASOPUST, T.; VASZIL, G.

Rok RIV

2009

Vydáno

12. 3. 2009

ISSN

1453-8245

Periodikum

Romanian Journal of Information Science and Technology (ROMJIST)

Ročník

12

Číslo

2

Stát

Rumunsko

Strany od

175

Strany do

189

Strany počet

15

URL

http://www.imt.ro/romjist/

BibTex

@article{BUT47968,
  author="Erzsébet {Csuhaj-Varjú} and Tomáš {Masopust} and György {Vaszil}",
  title="Cooperating Distributed Grammar Systems with Permitting Grammars as Components",
  journal="Romanian Journal of Information Science and Technology (ROMJIST)",
  year="2009",
  volume="12",
  number="2",
  pages="175--189",
  issn="1453-8245",
  url="http://www.imt.ro/romjist/"
}