Detail publikace

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T. MEDUNA, A.

Originální název

On Descriptional Complexity of Partially Parallel Grammars

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

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.

Klíčová slova

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

Autoři

MASOPUST, T.; MEDUNA, A.

Rok RIV

2008

Vydáno

17. 4. 2008

ISSN

0169-2968

Periodikum

Fundamenta Informaticae

Ročník

87

Číslo

3

Stát

Polská republika

Strany od

407

Strany do

415

Strany počet

9

URL

http://fi.mimuw.edu.pl/vol87.html

BibTex

@article{BUT49466,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Descriptional Complexity of Partially Parallel Grammars",
  journal="Fundamenta Informaticae",
  year="2008",
  volume="87",
  number="3",
  pages="407--415",
  issn="0169-2968",
  url="http://fi.mimuw.edu.pl/vol87.html"
}