Detail publikace

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Originální název

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Anglický název

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

Jazyk

en

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.

Anglický 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.

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",
  annote="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.",
  address="NEUVEDEN",
  chapter="47968",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Romanian Journal of Information Science and Technology (ROMJIST)",
  number="2",
  volume="12",
  year="2009",
  month="march",
  pages="175--189",
  publisher="NEUVEDEN",
  type="journal article - other"
}