Detail publikace

On Descriptional Complexity of Partially Parallel Grammars

Originální název

On Descriptional Complexity of Partially Parallel Grammars

Anglický název

On Descriptional Complexity of Partially Parallel Grammars

Jazyk

en

Originální abstrakt

In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors.

Anglický abstrakt

In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors.

BibTex


@article{BUT49466,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Descriptional Complexity of Partially Parallel Grammars",
  annote="In this paper, we improve some well-known results concerning descriptional
complexity of partially parallel grammars. Specifically, we prove that every
recursively enumerable language is generated by a four-nonterminal scattered
context grammar with no more than four non-context-free productions, by
a two-nonterminal multisequential grammar with no more than two selectors, or by
a three-nonterminal multicontinuous grammar with no more than two selectors.",
  address="NEUVEDEN",
  chapter="49466",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Fundamenta Informaticae",
  number="3",
  volume="87",
  year="2008",
  month="april",
  pages="407--415",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}