Detail publikace

Descriptional Complexity of Multi-Parallel Grammars

Originální název

Descriptional Complexity of Multi-Parallel Grammars

Anglický název

Descriptional Complexity of Multi-Parallel Grammars

Jazyk

en

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.

BibTex


@article{BUT48168,
  author="Tomáš {Masopust}",
  title="Descriptional Complexity of Multi-Parallel Grammars",
  annote="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.",
  address="NEUVEDEN",
  chapter="48168",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Information Processing Letters",
  number="2",
  volume="108",
  year="2008",
  month="march",
  pages="68--70",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}