Detail publikačního výsledku

Descriptional Complexity of Multi-Parallel Grammars

MASOPUST, T.

Originální název

Descriptional Complexity of Multi-Parallel Grammars

Anglický název

Descriptional Complexity of Multi-Parallel Grammars

Druh

Článek WoS

Originální abstrakt

This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.

Anglický abstrakt

This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.

Klíčová slova

formal languages, multi-parallel grammars, descriptional complexity

Klíčová slova v angličtině

formal languages, multi-parallel grammars, descriptional complexity

Autoři

MASOPUST, T.

Rok RIV

2010

Vydáno

31.03.2008

ISSN

0020-0190

Periodikum

INFORMATION PROCESSING LETTERS

Svazek

108

Číslo

2

Stát

Nizozemsko

Strany od

68

Strany do

70

Strany počet

3

URL

http://dx.doi.org/10.1016/j.ipl.2008.04.002

BibTex

@article{BUT48168,
  author="Tomáš {Masopust}",
  title="Descriptional Complexity of Multi-Parallel Grammars",
  journal="INFORMATION PROCESSING LETTERS",
  year="2008",
  volume="108",
  number="2",
  pages="68--70",
  issn="0020-0190",
  url="http://dx.doi.org/10.1016/j.ipl.2008.04.002"
}