Publication detail

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T. MEDUNA, A.

Original Title

On Descriptional Complexity of Partially Parallel Grammars

English Title

On Descriptional Complexity of Partially Parallel Grammars

Type

journal article in Web of Science

Language

en

Original Abstract

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.

English abstract

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.

Keywords

formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

RIV year

2008

Released

17.04.2008

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

407

Pages to

415

Pages count

9

URL

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"
}