Detail publikačního výsledku

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T.; MEDUNA, A.

Originální název

On Descriptional Complexity of Partially Parallel Grammars

Anglický název

On Descriptional Complexity of Partially Parallel Grammars

Druh

Článek WoS

Originální abstrakt

In this paper, we improve some well-known results concerningdescriptional complexity of partially parallel grammars. Specifically,we prove that every recursively enumerable language is generated by afour-nonterminal scattered context grammar with no more than fournon-context-free productions, by a two-nonterminal multisequentialgrammar with no more than two selectors, or by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Anglický abstrakt

In this paper, we improve some well-known results concerningdescriptional complexity of partially parallel grammars. Specifically,we prove that every recursively enumerable language is generated by afour-nonterminal scattered context grammar with no more than fournon-context-free productions, by a two-nonterminal multisequentialgrammar with no more than two selectors, or by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

MASOPUST, T.; MEDUNA, A.

Rok RIV

2010

Vydáno

17.04.2008

ISSN

0169-2968

Periodikum

FUNDAMENTA INFORMATICAE

Svazek

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